동적 계획법을 최적화하는 9가지 방법 (Chapter 1)
IOI , ICPC , algorithm , dynamic-programming , geometry , data-structure
동적 계획법을 최적화하는 9가지 방법 (Chapter 1)
동적 계획법(DP) 알고리즘의 시간 복잡도를 줄이는 기법에 대해서는 다양한 프로그래밍 대회에서 많이 출제된 바가 있다. 이러한 알고리즘은 굉장히 아름다운 방법으로 시간 복잡도를 줄이기 때문에 다양한 대회에서 인기가 많으나, 실제로 표준적인 알고리즘 교과서나 입문서에서 배우기는 힘든 내용이라 초심자가 시작하기 힘든 것이 단점이다.
현재 동적 계획법 최적화에 대해서 배울 수 있는 인터넷 자료들은 대부분 최신 자료가 아니기 때문에, 내가 알고 있는 동적 계획법 최적화 기법을 모두 소개함으로써 이 분야의 지식 격차를 줄이는 데 도움을 주려 한다.
이 글을 읽을 때는 이 최적화 기법들이 단순히 동적 계획법에만 국한되어 있지 않다는 점을 유의하는 것이 좋다. 예시 문제로 올라와 있는 문제들도 동적 계획법과 상관이 없을 수 있다. 이러한 최적화 기법을 DP 최적화 라고 부르는 이유는 단순히 이것이 DP 알고리즘을 최적화 하는 데 가장 자주 사용되기 때문이다. 비슷한 형태의 문제나 수식이 나올 경우 DP가 아니더라도 후술할 최적화 기법을 사용할 수 있다.
모든 연습 문제는 난이도 순으로 정렬하려고 노력하였다. 글이 너무 길기 때문에 3단원으로 분할한다.
1. Convex Hull Optimization
- Recurrence: $DP[i] = Min_{j < i}(DP[j] + B[j] \times A[i])$
- Condition: None (See below)
- Naive Complexity: $O(n^2)$
- Optimized Complexity: $O(n \log n)$ ($O(n)$ in special cases)
컨벡스 헐 최적화는 동적 계획법 최적화 중 가장 간단한 형태에 속한다. 특수한 경우에는 매우 짧은 코드를 사용하여 최적화할 수 있고, 일반적인 경우에도 조금 더 복잡하지만 효율적으로 해결하는 방법이 이제는 알려져 있다. 이 최적화에 대해서는 Convex Hull Trick — Geometry being useful 글을 참고하라.
$B[i]$ 가 비감소라는 조건이 없을 때의 풀이에 대해서 몇가지 더 첨언하자면:
- Sqrt Decomposition를 사용하면 특정 자료구조를 배울 필요 없이 문제를 해결할 수 있다. 직선들을 기울기 순으로 정렬해서 관리하는 “주 저장소”, 아무 순서로 관리하는 “부 저장소” 를 두자. 기본적으로 모든 직선을 부 저장소에 삽입한 후 단순히 부 저장소에 있는 모든 직선을 순회하면서 쿼리를 처리한다. 만약 부 저장소의 크기가 $\sqrt n$ 을 초과한다면, 주 저장소에 현재 있는 직선들에 Merge sort를 하듯이 기울기 순서로 끼워넣은 후, 다시 Convex hull optimization 구조를 만들어 준다. 이렇게 되면 주 저장소에는 이분 탐색을 통해 $O(\log n)$ 시간에 쿼리를 , 부 저장소에는 단순히 $O(\sqrt n)$ 시간에 쿼리를 처리해 줄 수 있다. 고로 시간 복잡도는 $O(n\sqrt n)$ 이고, 상수가 작아 $O(n \log n)$ 에 비해 많이 느리지 않다 ($n = 200\,000$ 일 때 Li-Chao Tree에 비해 2배 정도). 이를 일반화한 Bentley-Saxe method를 사용하면 시간 복잡도가 $O(n \log n)$ 으로 줄어들지만, 실제 수행 시간은 거의 개선되지 않는다. 이에 대해서는 Solution to USACO FEB15. Fencing the Herd, 혹은 General ideas 4번 항목을 참고하라.
- 이진 탐색 트리를 사용하여 $B[j]$ 가 정렬된 순서대로 직선을 관리할 수 있다면 문제를 해결할 수 있다. 직선을 삽입한 후 양 옆을 순서대로 탐색하면서 더 이상 최적이 아닌 직선들을 삭제해주면 amortized $O(\log N)$ 시간에 문제를 해결할 수 있기 때문이다. 고로 Treap 등의 BBST를 사용하거나, STL set을 매우 잘 사용해 주면 문제를 해결할 수 있다. 일반적으로 이를 구현하는 것은 매우 힘들고, 본인도 하지 못한다. 하지만, 팀노트 등 prewritten code를 사용할 수 있는 상황이라면, 이를 매우 짧고 직관적으로 구현한 LineContainer 루틴을 복사하여 사용하는 것이 가장 효율적이다. 이 부분에 대해서는 위 글의 댓글 부분을 참고하라.
- Li-Chao Tree라는 자료구조를 사용해도 직선들을 관리할 수 있다. LineContainer에 비해서 시간이나 메모리가 비효율적이고 까다로운 편이라 추천하지는 않는다. 하지만 LineContainer보다 개념이 간단하기 때문에 빠르면서 이해하기 좋은 구현을 원한다면 이 자료구조를 추천한다. Li-Chao Tree는 굳이 일차함수가 아니더라도 특수한 경우에는 다른 함수들도 처리할 수 있다는 장점이 있다. 본인은 이 자료구조를 모르기 때문에 추가적으로 설명하지 않는다. Li-Chao Tree에 대해서는 Convex Hull Trick in cp-algorithms.com 에 잘 설명되어 있다.
Practice problems
- Codeforces: Kalila and Dimna in the Logging Industry
- IOI 2002: Batch Scheduling
- APIO 2010: Commando
- APIO 2014: Split the Sequence
- USACO Gold MAR08: Land Acquisition
- CEOI 2017: Building Bridges
- BOI 2012: Balls
2. Divide and Conquer Optimization
- Recurrence: $DP[i][j] = Min_{k < j}(DP[i-1][k] + C[k][j])$
- Condition: $C[i][j]$ is a Monge array.
- Naive Complexity: $O(kn^2)$
- Optimized Complexity: $O(kn \log n)$ ($O(kn)$ possible)
어떠한 2차원 배열이 Monge array 라는 것은, 임의의 $a \le b \le c \le d$ 에 대해 $C[a][c] + C[b][d] \le C[a][d] + C[b][c]$ 라는 것을 만족한다. 일반적으로 $C[i][j]$ 는 구간 $[i, j]$ 를 사용했을 때의 비용을 뜻하니, 이 식은 즉 한쪽 구간이 다른쪽 구간을 포함하고 있으면, 그렇지 않도록 풀어주는 것이 이득 이라는 것을 의미한다. (비슷한 상황은 Submodular inequality에서도 등장한다.)
D&C Optimization은 다음과 같은 Lemma를 기반으로 위 동적 계획법을 최적화한다:
-
Lemma. 임의의 $c < d$ 에 대해, $opt_c$ 를 $DP[i-1][k] + C[k][c]$ 를 최소화하는 $k$, $opt_d$ 를 $DP[i-1][k] + C[k][d]$ 를 최소화하는 $k$ 라고 정의하자. (만약 여러 $k$가 있으면 가장 작은 $k$ 를 고른다.) 이 때 $opt_c \le opt_d$ 를 만족한다.
-
Proof. 그렇지 않다고 하자. 즉 $opt_c > opt_d$ 이다. 다음과 같은 2개의 식을 유도할 수 있다:
- $DP[i-1][opt_c] + C[opt_c][c] < DP[i-1][opt_d] + C[opt_d][c]$
- $DP[i-1][opt_d] + C[opt_d][d] \le DP[i-1][opt_c] + C[opt_c][d]$
두 식을 더하면 $C[opt_c][c] + C[opt_d][d] < C[opt_d][c] + C[opt_c][d]$ 라는 식이 유도된다. $b = opt_c, a = opt_d$ 으로 두면 Monge array의 정의에 모순됨을 볼 수 있다.
이렇게 $opt_c \le opt_d$ 라는 성질을 보이면 분할 정복 최적화를 사용할 수 있다. 실제 최적화가 어떠한 식으로 이루어지는가는 https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html 내용을 참고하라.
몇 가지 혼동해서는 안 되는 사실은 다음과 같다:
- Monge array가 분할 정복 최적화의 필요충분조건은 아니다. 분할 정복 최적화는 최적해의 단조성만을 필요로 한다. 아래에 잠시 설명할 SMAWK 역시 그렇다. 다만 분할 정복 최적화가 필요한 대부분의 상황에서 Monge array의 조건이 관찰될 뿐이다.
- Monge array라는 배열이 실제로 필요한 것이 아님에 유의하자: $C[i][j]$ 가 배열로 존재하지 않아도, 예를 들어 $c(i, j)$ 라는 함수를 $O(1)$ 시간에 호출할 수 있으면 상관이 없고, 만약 함수 호출 시간이 (예를 들어 자료 구조 등을 사용하기 때문에) $O(\log N)$ 정도 걸린다면 최적화된 시간 복잡도에 이 호출 시간만큼 곱해주면 된다.
어떠한 Monge array $C$ 에 대해서 $C^\prime[i][j] = C[i][j] + DP[x-1][i-1]$ 이라고 정의하자. 위 부등식에 대입하면 $C^\prime$ 역시 Monge array임을 쉽게 알 수 있다. 어떠한 Monge array에 대해서, 각 $i$ 에 대한 $min_j C[i][j]$ 를 빠르게 구하는 알고리즘을 생각해 보자. 이는 위에서 사용한 Divide and Conquer Optimization을 사용해서 $O(n \log n)$ 에 할 수 있지만, SMAWK 라는 알고리즘을 사용하면 이보다 더 빠른 $O(n)$ 시간에 할 수 있음이 알려져 있다. 이 문제에서는 각 $i$ 에 대한 최소 $j$ 가 아니라 그 반대를 구하는 것이지만 동일한 알고리즘을 사용할 수 있다. 고로 SMAWK 알고리즘을 사용하면 $O(kn)$ 시간에도 Divide and Conquer Optimization을 수행할 수 있다. SMAWK 알고리즘에 대해서는 다음 링크에서 배울 수 있다: 강의 자료 예시 코드 Wikipedia.
Practice problems
- Codeforces: Ciel and Gondolas
- Hackerrank: Guardians of the Lunatics
- World Finals 2016: Branch Assignment
- JOI Spring Camp 2019: Cake 3
- IOI 2014: Holiday
- Codeforces: Yet another minimization problem
- World Finals 2017: Money for Nothing
- NAIPC 2016: Jewel Thief
3. Monotone Queue Optimization
- Recurrence: $DP[i] = Min_{j < i}(DP[j] + C[j][i])$
- Condition: $C[i][j]$ is a Monge array.
- Naive Complexity: $O(n^2)$
- Optimized Complexity: $O(n\log n)$
Monotone Queue Optimization은 2번에서 나온 Divide and Conquer Optimization, 그리고 1번에서 나온 Convex hull optimization(CHT) 의 특수 케이스를 모두 일반화한다. D&C Optimization이 어떻게 일반화되는지는 나중에 살펴볼 것이고, CHT가 최적화되는 이유는 다음과 같이 간단히 보일 수 있다.
- Lemma. $A[i] \ge A[i + 1], B[i] \le B[i + 1]$ 일 때, $C[i][j] = B[i] \times A[j]$ 는 Monge array이다.
- Proof: $B[a]\times A[c] + B[b] \times A[d] \le B[a] \times A[d] + B[b] \times A[c]$, $(B[a] - B[b]) \times (A[c] - A[d]) \le 0$.
고로, 기울기와 쿼리 모두에 단조성이 있는 CHT은 Monotone Queue Optimization으로 풀 수 있는 문제에 포함된다. 이러한 방식이니, 자연적으로 CHT과 문제 해결이 유사함을 짐작할 수 있다.
Monotone Queue Optimization에 대해 논의하기 전 다음과 같은 Lemma를 사용하자.
- Lemma. 어떠한 $i < j < k$ 에 대해서, $DP[i] + C[i][k+1] \le DP[j] + C[j][k+1]$ 이면 $DP[i] + C[i][k] \le DP[j] + C[j][k]$ 가 만족하고, $DP[i] + C[i][k] \ge DP[j] + C[j][k]$ 이면 $DP[i] + C[i][k+1] \ge DP[j] + C[j][k+1]$ 을 만족한다.
- Proof.
- 첫번째 식: $DP[i] - DP[j] \le C[j][k+1] - C[i][k+1] \le C[j][k] - C[i][k]$ 이기에 성립.
- 두번째 식: $DP[j] - DP[i] \le C[i][k] - C[j][k] \le C[i][k+1] - C[j][k+1]$ 이기에 성립.
이 사실은, 임의의 $i < j$ 에 대해서 어떠한 지점 $cross(i, j)$ 가 있어서, $cross(i, j) \le k$ 이면 $DP[j] + C[j][k]$ 가 더 작은 값을 주고, $cross(i, j) > k$ 이면 $DP[i] + C[i][k]$ 가 더 작은 값을 준다는 것이다. (실제 구현 시 “이상, 초과”인지를 꼼꼼하게 따지자.) 이러한 $cross(i, j)$ 는 이분 탐색을 사용하여 $O(\log n)$ 에 찾을 수 있다. CHT와 비교했을 때 이 부분은 어떠한 두 선분의 교점을 찾는 것에 비유된다는 것을 생각하면 이해가 쉽다. 두 선분의 교점은 단순한 방정식 해결로 쉽게 찾을 수 있으나, 이 경우에는 그렇지 않기 때문에 이분 탐색을 사용한다. 이러한 면에서 $DP[i] + C[i][x]$ 는 직선하고는 전혀 상관이 없으나, 직선과 비슷한 함수라고 상상할 수 있다.
이제 CHT에서 사용된 풀이법을 그대로 적용하자. $DP[i] = min(DP[j] + C[j][i])$ 식을 해결할 때, $[i, n]$ 에 있는 원소들에 대해서 답의 후보가 될 수 있는 모든 $j$ 를 데큐 $Q$ 에 순서대로 저장한다. $Q$ 에는 답의 후보가 될 수 있는 $j$ 만이 저장되어 있기 때문에, $cross(Q_i, Q_{i+1}) < cross(Q_{i + 1}, Q_{i + 2})$ 를 만족한다. 만약 등호가 반대라면, $Q_{i+1}$ 은 어떠한 쿼리 지점에 대해서도 $Q_i, Q_{i+2}$ 보다 나은 선택이 아니기 때문이다. 만약 이러한 데큐 $Q$ 를 관리했다면, 최소값을 찾는 것은 $Q$ 를 앞에서부터 보면서, $cross(Q_0, Q_1) < i$ 일 때까지 $Q_0$ 을 제거하는 식으로 찾을 수 있다.
새로운 원소를 삽입할 때는, $cross(Q_i, Q_{i+1}) < cross(Q_{i + 1}, Q_{i + 2})$ 라는 불변량이 깨지지 않도록 주의해야 한다. 데큐의 맨 뒤에 원소를 삽입한다면, 불변량이 깨지는 위치는 데큐의 끝쪽 위치이기 때문에, CHT에서와 유사하게 이 쪽에서만 수정을 해 주면 된다. 정확히는, 만약 데큐의 마지막 두 원소를 $x, y$ 라고 했을 때 ($x < y$), $cross(x, y) \geq cross(y, i)$ 라는 식이 만족한다면 $y$가 $x, i$에 비해 최적인 위치가 없다는 것을 알 수 있다. 이러한 상태가 해결될 때까지 큐의 뒤를 비워준 후, 맨 마지막에 $i$ 를 넣어주면, 불변량이 다시 성립하게 되어 쿼리를 처리하기 좋은 상태가 된다.
이 알고리즘은 $cross(i, j)$ 함수를 $O(n)$ 번 호출하게 되고, 각 $cross(i, j)$ 함수를 계산하는 데 $O(\log n)$ 시간이 소모되기 때문에, $O(n \log n)$ 시간을 사용한다. $cross(i, j)$ 함수를 계산하는 데 $O(1)$ 이 걸리게 할 수 있다면, 이 알고리즘은 $O(n)$ 시간을 사용한다.
마지막으로, D&C Optimization과 같은 상황에서도 똑같은 최적화가 성립하는 이유는, 위 Lemma에서 $DP[i], DP[j]$ 항을 $DP[i-1][j], DP[i-1][k]$ 정도로 바꿔도 차이가 없기 때문이다. 고로 위에서 이야기한 최적화 방법을 그대로 적용할 수 있다.
Practice Problems
- Codeforces: Kalila and Dimna in the Logging Industry
- IOI 2002: Batch Scheduling
- 위에서 사용한 모든 Divide and Conquer Optimization 문제들
- 서울대학교 2019. 꽃집
- 길이 $N$ 의 양의 정수로 이루어진 수열 $A[1], A[2], \cdots, A[N]$ 이 있다. 이를 $K$ 개 이하의 연속 구간으로 분할할 것이다. 구간 $[i, j]$의 비용은 $(\sum_{k = i}^{j} A[k]) \times (j - i + 1)$ 일 때 비용 합의 최소는 얼마인가? 문제에는 추가적으로 수열이 증가한다는 ($A[i] \le A[i + 1]$) 조건이 붙어 있으나 이 조건이 없어도 문제를 해결할 수 있다.
- 이 문제는 5번에서 소개할 Aliens Trick을 추가적으로 사용하니, 5번 단락을 읽고 시도하자.
- USACO 2019 Feb. Mowing Mischief (Challenge)