문제 출처 : 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..
문제 출처 : https://www.acmicpc.net/problem/11066 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ) 해설합쳐야 하는 파일을 두 수열로 나눌 수 있다. 최적으로 합쳐야 하는 구간을 i ~ j 라고 할 때 임의의 k에 대해 ( i 0 ? mem[i - 1] : 0); } int main() { int t; scanf("%d", &t); for (; t--; ) { int i, j, n; memset(dp, -1, sizeof dp); scanf("%d", &n); for (i = 0; i 0 ? mem[i - 1] : 0); } printf("%d\..
문제 출처 : https://www.acmicpc.net/problem/1715 문제 해결에 필요한 알고리즘 : 그리디 알고리즘 해설 가장 작은 두 수끼리 계속 합쳐주는 것이 가장 최적이다. priority queue를 이용하여 문제를 해결 할 수 있다. 모든 수를 큐에 삽입한 후 가장 작은 두 수를 꺼내 연산한 뒤 결과를 다시 큐에 넣어주면 된다. 이렇게 큐에 한가지의 숫자가 남을 때 까지 하면 최소로 비교하는 횟수를 알 수 있다. 정당성 증명 S(A, b)를 A라는 수의 집합과 b라는 수를 포함하는 카드의 집합이라고 정의한다. MIN(S) 는 수의 집합에서 가장 최적으로 비교하는 횟수라고 정의한다. S(A, b), S(A, c)가 있을 때 b > c 라고 하면, MIN(S(A, b)) > MIN(S(..
문제 출처 : https://www.acmicpc.net/problem/2156 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ) 해설마시는 순서는 상관이 없기에 포도주를 1번부터 순서대로 마신다고 가정함. dp와 ar의 인덱스는 0번부터 시작함. i = 0 일 때dp[i][2] = dp[i][0] = 0dp[i][1] = ar[i] i > 0 일 때dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2])dp[i][1] = dp[i - 1][0] + ar[i]dp[i][2] = dp[i - 1][1] + ar[i] dp[선택한 포도주의 번호][연속으로 마신 포도주의 개수] = 마시는 포도주 양의 최댓값ar[포도주의 번호] = 포도..
문제 출처 : https://www.acmicpc.net/problem/9084 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ) 해설 이 문제는 간단한 동적계획법으로 해결이 된다. 아이디어는 간단하다. 동전을 순차적으로 고를 때 각 동전마다 몇개씩 고를지 계산하면 된다. N개의 동전종류가 남았을 때 M원을 만들 수 있는 경우의 수를 DP[N][M] 이라고 가정하고 부분문제로 나누면 동전 종류가 N - 1개가 남았고 현재 동전을 1개 선택한 경우 동전 종류가 N - 1개가 남았고 현재 동전을 2개 선택한 경우 ... 모든 경우의수의 합이 정답이 된다. 따라서 위의 점화식을 얻게 된다. 시간복잡도 DP테이블을 다 채우는데는 N * M의 시간복잡도를 가진다. 또 find함수 내..
문제 출처 : https://www.acmicpc.net/problem/16194 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ) 해설 이 문제는 정해진 갯수의 카드를 최소값으로 사는 문제이다. 1 ~ N 개의 카드세트가 있을 때, N개의 카드를 가장 싸게 구하는 문제이다. 이 문제는 간단한 부분 문제로 나눌 수 있다. N개의 카드를 살 때 가장 싸게 사는 방법은 선택한 카드의 갯수만큼 가장 싼 값에 산다고 가정했을 때, 이 중 하나일 것이다. 카드 N개를 산다. 카드 N - 1개와 1개를 산다. 카드 N - 2개와 2개를 산다. ... N - 1개를 산다고 가정하면 N - 1개를 최솟값으로 살 수 있는 경우를 탐색해야한다. 이 때 (N - 1) - 1개와 1개를 산다고 ..
문제 출처 : https://www.acmicpc.net/problem/16172 문제 해결에 필요한 알고리즘 : KMP ( Knuth Morris Pratt ) 알고리즘 해설 알파벳과 숫자로 이루어진 문자열에서 숫자를 무시하고 검색하여 문자열이 포함되어있는지 판단하는 문제이다. 문자열 길이가 1,000,000 이므로 일반적인 탐색방법으로는 해결이 불가하다. 그래서 빠른 검색알고리즘인 KMP를 적용하면 된다. KMP 알고리즘은 한번의 순회로 문자열을 검색하는 방법이다. 간단한 예시로 nabananbananaba 라는 문자열에서 nanaba를 검색한다고 했을 때 일반적인 알고리즘이라면 첫 na까지 검색하고 b가나와 맞지않으므로 a부터 검색을 시작한다. 하지만 이미 na까지 검색을 했다면 a로 탐색을 시작하..
문제 출처 : https://www.acmicpc.net/problem/16174 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ), BFS ( Breadth First Search ) 알고리즘 해설쩰리가 움직이기 시작하는 위치인 (0, 0) 부터 queue에 넣어 순차적으로 탐색을 시작한다. 쩰리는 오른쪽 또는 아래쪽만 이동이 가능하기 때문에 선택가능한 선택지는 두가지이하다. 맵 밖을 나가지 않으면서 이미 방문했던 칸이 아닌 곳을 계속 queue 에 넣어주며 (N - 1, N - 1)을 도달할 수 있는지 확인하면 된다. (N - 1, N - 1)좌표로 이동했다면 승리, 이동하지 못했다면 패배가 된다. 정당성 증명이미 방문한 칸을 다시 탐색하지 않아도 되는 이유는 결과가 중..