문제 출처 : https://www.acmicpc.net/problem/16975 문제 해결에 필요한 알고리즘 : Segment Tree Lazy Propagation 해설 / 시간복잡도1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다.2 x: Ax 를 출력한다.이 조건에서 1번 문제는 Segment Tree를 Lazy하게 업데이트 하면 으로 구간 덧셈을 업데이트 할 수 있다. 또 2번 조건도 Segment Tree 검색도 으로 검색이 가능하다. 그래서 으로 해결할 수 있다. 수열과 쿼리 21 코드 [ C ] #include #define LEFT(I) (I y || r = x && r > 1; return find(LEFT(I), l, mid, x, ..
문제 출처 : https://www.acmicpc.net/problem/3101 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ), 구현 해설이 문제는 토끼가 움직이며 밟는 칸의 값을 다 더하는 문제이다. 직관적인 방법으로는 DP를 이용해 행렬을 다 채운 뒤 이동하며 나오는 값을 다 더해 구할수도있다. 하지만 ( 1 n) ++y; --x; break; case 'D': if (x >= n) -- y; ++x; break; case 'L': if (x
문제 출처 : https://www.acmicpc.net/problem/2243 문제 해결에 필요한 알고리즘 : 펜윅 트리 ( Fenwick Tree ), 이분 탐색 해설사실 이 문제는 Red-Black Tree 나 Treap 같은 자료구조를 이용해 해결 할 수 있는 문제다. 하지만 펜윅 트리를 이용해서 간단하게 구현이 가능하다. 번호순대로 사탕을 가지고 있을 때 정렬된 사탕 기준으로 k ( k는 임의의 정수 )번째 사탕을 구하는 문제이다. 누적합 ( DP ) 를 이용해서 문제를 해결할 수 있지만, 업데이트속도가 매우 느리다. 그래서 이 부분을 펜윅트리로 대체해 빠르게 업데이트가 가능하다.펜윅트리를 이용해 누적합을 가지고 있을 때 k번째 사탕을 구하기 위해 이분탐색을 사용하면 된다. lower bound..