개인사

리뷰 세그먼트 트리를 응용하여 히스토그램 상에서 가장 큰 면적을 구하는 문제https://www.acmicpc.net/problem/6549 전역 변수lst : 히스토그램의 높이 정보를 저장할 정수형 배열, 최대 히스토그램 크기 10만으로 초기화 해준다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, lst의 4배 40만으로 크기를 초기화 해준다.n : 히스토그램의 최대 갯수를 저장할 정수형 변수  함수1. initvoid init() 각 테스트 케이스 마다 lst와 tree를 0으로 초기화 해주는 함수 2. inputvoid input() 데이터를 입력 받고 히스토그램 높이 정보를 lst배열에 초기화 해주는 함수 3. buildvoid build(ll node, ll start, ll end) ..

리뷰 세그먼트 트리의 기초가 되는 문제인듯 싶다, 구간 업데이트 쿼리가 아닌 리프 노드까지 도달해야 하는 문제수열과 쿼리 시리즈 부터 풀다보니 이런 기초 세그를 응용하는 문제가 약해서 생각의 폭을 넓혀야 겠다 ㅠhttps://www.acmicpc.net/problem/2243 전역 변수tree : 세그먼트 트리 정보를 저장할 정수형 배열, 사탕의 맛 개수가 최대 100만이므로 400만 이상의 크기로 세팅한다. 함수1. updatevoid update(int node, int start, int end, int idx, int val) 매개변수 idx의 맛을 가진 사탕의 개수를 val만큼 더해준다.val에는 음수가 올 수 있으나 문제에 없는 사탕을 꺼내는 경우와 같은 잘못된 입력은 주어지지 않는다. 라고 ..

리뷰 앨범이나 사진이 중복될 경우 출력하는 문자열이 잘못되어서 계속 틀렸다... 문제를 잘 읽자 ㅠLinked List를 사용한다면 시간을 더 줄일 수 있을 것 같은데 아무래도 해시맵의 키를 경로의 합인 문자열을 사용하다 보니 해시 충돌이 나서 더 이상 시간을 줄이기엔 무리가 있는 것 같다.해시맵을 통해 절대 경로를 key로 사용하는 방식으로 문제를 풀었다.https://www.acmicpc.net/problem/20541 전역 변수Data : 앨범 정보를 저장할 구조체, 부모 앨범명, 현재 앨범명, 현재 앨범에 존재하는 앨범 및 사진 집합이 저장된다.dic : 맵 구조를 나타낼 해시맵, 앨범 이름을 키로 받고, 해당 폴더 정보 Data 구조체를 값으로 저장한다.del_album, del_photo : ..

리뷰 수열의 특정 구간에 XOR연산을 진행하고, 특정 인덱스의 값을 뽑아 출력하는 문제https://www.acmicpc.net/problem/14245해당 문제의 심화 버전으로 구간에 xor를 적용하여 출력하는 문제가 있다. [P3] 백준 12844번 XOR C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리리뷰 XOR연산에 대해 재정립 하는 시간이 되었다.https://www.acmicpc.net/problem/12844 전역 변수MAX_N : 노드의 최대 개수를 저장할 인트형 상수 정수, 50만으로 초기화 해준다.nodes : 노드의 정보를 저장할zzzz955.tistory.com   전역 변수MAX_N : 노드의 최대 개수를 정의할 정수형 상수 변수, 50만으로 초기화 해준다.nodes : 수열..

리뷰 구간의 합이 특정 값이 되는 구간의 개수를 구하는 문제https://www.acmicpc.net/problem/2015 전역 변수dic : 특정 구간의 누적합을 key로 갖고, 그러한 누적합의 개수를 value로 받는 해시맵 long long, int 타입total, ans : 누적합 정보를 저장할 변수total, 인접한 수열의 합이 k인 수열의 개수 ans, long long타입으로 초기화 한다.n, k, : 수열의 길이 n, 찾을 값 k,  함수없음  문제풀이n, k를 입력 받고, sum배열의 1 ~ n번째 인덱스에 누적합 정보를 저장해 준다.다시 1 ~ n번의 정보를 탐색하며 ans에 현재 누적합 인덱스에서 k를 뺀 값의 개수를 더해준다.이후 현재 누적합 정보를 키로 갖는 dic의 개수를 증가..

리뷰 XOR연산에 대해 재정립 하는 시간이 되었다.https://www.acmicpc.net/problem/12844 전역 변수MAX_N : 노드의 최대 개수를 저장할 인트형 상수 정수, 50만으로 초기화 해준다.nodes : 노드의 정보를 저장할 정수형 배열, MAX_N크기로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화 한다.lazy : 업데이트 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화 한다.n, m : 노드의 개수를 저장할 정수 변수 n, 쿼리의 개수를 저장할 정수 변수 m 함수1. buildvoid build(int node, int start, int end) 세그먼트 트리를 초기화 해주는 함수 2. propagatevoid ..

리뷰 2048(Easy)의 어려운 버전, 재귀의 깊이가 기존 5에서 10으로 늘어났다. [G1] 백준 12100번 2048 (Easy) C++ 백트래킹, 구현, 시뮬레이션, 브루트포스 알고리즘리뷰 2048게임을 구현하는 문제, 시뮬레이션만 잘 작성하면 쉽게 풀 수 있으나 문제를 잘 읽어보아야 할듯 하다.https://www.acmicpc.net/problem/12100 문제 풀이전역 변수n : 맵의 행, 열을 저장할 변수anszzzz955.tistory.com 가지치기를 최소 두개를 추가해 줘야 시간 초과를 막을 수 있는 문제인 듯https://www.acmicpc.net/problem/12094 전역 변수n, ans : 맵의 행과 열의 길이를 저장할 정수형 변수 n, 최대값을 저장할 변수 ansmap ..

리뷰 느리게 갱신되는 세그먼트 트리 문제 치고 굉장히 짧고 쉬운 문제!https://www.acmicpc.net/problem/1395 전역 변수MAX_N : 스위치의 최대 개수를 정의할 정수형 상수 변수tree : 세그먼트 트리 정보를 저장할 배열 MAX_N * 4 크기로 초기값은 0이다.lazy : 업데이트 갱신을 적용하기 위한 트리 배열 MAX_N * 4 크기로 초기값은 0이다.n, m : 스위치의 개수를 저장할 변수 n, 쿼리의 개수를 저장할 변수 m 함수1. propagatevoid propagate(int node, int start, int end) 현재 노드에 갱신이 필요하다면 갱신을 진행하고 자식 노드에 지연 업데이트를 기록하는 함수이다.현재 노드에 갱신이 필요하다면 구간의 길이 - 자신..

리뷰 간만에 풀어본 해시맵 문제, 파이썬으로 숙달한 사람은 map에 익숙해 지는 것 같다.https://www.acmicpc.net/problem/21944 전역 변수n, m : 초기에 입력되는 문제의 개수를 저장할 정수형 변수 n, 쿼리의 개수를 저장할 정수형 변수 mProb : 문제의 난이도와 알고리즘 분류 정보를 저장할 구조체probs : 문제 정보를 저장할 Prob 타입 배열, 문제 번호를 index로 사용하여 관리, 크기는 최대문제 번호 10만 + 1rec1 : recommed입력 시 문제 정보를 출력할 맵, 알고리즘 분류를 키로 가지며 int와 set 쌍으로 관리해 준다.rec2 : 알고리즘 분류 상관 없이 문제의 난이도로만 출력을 관리할 set, pair을 통해 난이도와 문제 번호를 관리한다..

리뷰 쿼리로 부분 수열에 특정 수를 더하기, 곱하기, 대체하기가 나오는 구간합 문제느리게 갱신되는 세그먼트 트리의 개념을 익혔다고 섣불리 덤볐다가 혼쭐났다.https://www.acmicpc.net/problem/13925 문제 풀이전역 변수MAX_N : 노드의 최대 개수를 지정할 정수형 상수 변수MOD : MOD 연산을 해줄 정수형 상수 변수, 10억 + 7로 고정이다.nodes : 수열의 정보가 저장될 정수형 배열, MAX_N 크기로 초기화 해준다.tree : 세그먼트 트리 정보가 저장될 정수형 배열, MAX_N * 4 크기로 초기화 해준다.n, m : 수열의 길이를 저장할 변수 n, 쿼리의 개수를 저장할 변수 mLazy : 세그먼트 트리의 구간 더하기(add), 곱하기(mul), 대체하기(set)를..