동적 계획법을 최적화하는 9가지 방법 (2/4)

4. Knuth's Optimization

• Recurrence: $DP[i][j] = Min_{i \le k < j}(DP[i][k] + DP[k + 1][j] + C[i][j])$
• Condition: $C[i][j]$ is a Monge array, and satisfies $C[a][d] \ge C[b][c]$ for $a \le b \le c \le d$.
• Naive Complexity: $O(n^3)$
• Optimized Complexity: $O(n^2)$

Knuth Optimization은 어떠한 구간을 쪼개는 형태의 동적 계획법을 최적화한다. Optimal Binary Search Tree 라고 알려진 문제를 Knuth가 $O(n^2)$ 동적 계획법으로 해결할 때 사용되었기 때문에 Knuth의 이름이 붙었다. 자주 등장하는 문제가 아니고, 증명이 그닥 아름다운 것도 아니기 때문에 대회에서 유용하지는 않다고 생각하나, 아이디어가 간단한 편이기 때문에 짧게 설명한다.

$C[i][j]$ 가 Monge array이고, 추가적으로 $C[a][d] \geq C[b][c]$ 를 만족한다고 하자. 만약 $opt[i][j]$ 를 $DP[i][j]$ 에서 최솟값을 주는 $k$ (여러 개 있을 경우 가장 왼쪽) 이라고 정의할 때, 다음 성질이 성립한다:

• Lemma. $opt[i][j-1] \le opt[i][j] \le opt[i+1][j]$
• Proof. 증명은 간단하지 않다. Efficient dynamic programming using quadrangle inequalities (Yao. 1980) 을 참고하라.

위 Lemma를 사용하면, $j - i$ 가 증가하는 순서대로 DP 테이블을 채웠을 때 $O(n^2)$ 의 시간 복잡도를 얻을 수 있다. $j -i = 0$ 일 경우 $DP[i][j]$ 와 $opt[i][j]$ 를 바로 얻을 수 있고, 그 이상일 때는 $opt[i][j-1] \le k \le opt[i+1][j]$ 구간을 순회하면 되기 때문이다. 이렇게 순회했을 경우 총 루프가 도는 횟수는, $j - i = k$ 라고 두었을 때 $\sum (opt[i+1][i+k] - opt[i][i+k-1]) = (opt[n-k+1][n] - opt[1][k]) \le n$ 으로, 하나의 $j - i$ 에 대해서 $O(n)$ 이니 총 $O(n^2)$ 이다.

$C[i][j]$ 가 특수한 형태의 경우일 때에는 굉장히 빠른 시간 복잡도에 해결할 수 있는 방법들도 존재한다.

• Optimal Binary Search Tree 문제는 $C[i][j] = \sum_{k = i}^{j} A[k]$ 같은 형태의 부분합으로 정의된다. 이 때, Garsia-Wachs algorithm 은 $O(n \log n)$ 에 최적해를 찾을 수 있다.
• Matrix Chain Multiplication 문제는 $C[i][j] = A[i] \times A[k+1] \times A[j + 1]$ 의 형태로 정의된다. $C[i][j]$ 가 위 조건을 만족하지 않지만 Hu-Shing Algorithm으로 $O(n \log n)$ 에 최적해를 찾을 수 있다.

Practice problems

• Andrew Stankevich Contest 10. Order-Preserving Codes (Optimal Binary Search Tree 문제와 동일한 문제이다.)
• JAG Autumn 2015. Optimal Tournament
• Atcoder: 最適二分探索木

5. Aliens Trick (Lagrange Optimization)

• Recurrence: $DP[i][j] = Min_{k < j}(DP[i-1][k] + C[k+1][j])$
• Condition: $DP[x][n]$ is convex (which is implied if $C[i][j]$ is a Monge array)
• Naive Complexity: $O(kn^2)$
• Optimized Complexity: $O(n^2 \log |W|)$

이 방법은 IOI 2016에 "Aliens" 라는 문제가 나온 이후로 유명해졌기 때문에 흔히 "Aliens Trick" 이라는 이름으로 불린다. Lagrange multiplier와 유사한 아이디어를 사용하기 때문에 "Lagrange Optimization"이라고 부르거나, Aliens보다 일찍 중국에 소개한 Qinshi Wang의 이름을 따 wqs binary search 라고 부르기도 한다.

다음과 같은 예시 문제를 생각하자 (이 문제는 APIO 2014: Split the Sequence와 동일한 문제이다).

양의 정수로 이루어진 길이 $n$ 의 수열을 $k$ 개의 연속 구간으로 나누려고 한다. 연속 구간 $[i, j]$ 의 비용은 $(\sum_{k = i}^{j} A[k])^2$ 이다. 최소 비용은 얼마인가?

이 문제의 해의 경우 다음과 같은 성질을 가지고 있다:

• $k$가 커질수록 답은 항상 감소한다. ($(a+b)^2 \geq a^2 + b^2$ 라서, $k$ 의 최적해에서 아무거나 쪼개도 답이 줄어든다.)
• $k$에 대한 조건이 없다면, $O(n)$ 에 문제를 해결할 수 있다. 위에서 배운 Convex Hull Trick을 사용하면 된다. (그렇게 어렵지 않은데, 이 부분을 이해하지 못해도 글을 읽는 데 지장은 없다.)
• $k$에 대한 조건이 없다면, $k$ 가 커질수록 답이 감소하니, $k = n$ 으로 하여 모든 연속 구간이 1의 길이를 가진 해가 반환될 것이다.

$k$ 에 상관없이 문제를 해결한다면. $DP[i] = min_{j < i}(DP[j] + Cost[i][j])$ 형태의 점화식이 나온다. 이를 $DP[i] = min_{j < i}(DP[j] + Cost[i][j] + 10^{100})$ 으로 바꾸면 어떻게 될까? 각 구간을 만들 때마다 어마어마한 비용을 지불하기 때문에, $[1, n]$ 구간으로만 분할하는 것이 답이 된다. 이제 일반화해서 우리가 $\lambda$ 라는 적당한 숫자를 정했다고 하자. $DP[i] = min_{j < i}(DP[j] + Cost[i][j] + \lambda)$ 와 같은 DP는, $\lambda$ 가 커질 경우 전반적으로 $k$ 의 개수를 줄일 것이며, $\lambda$ 가 작아질 경우 $k$ 의 개수를 늘릴 것이다.

만약 우리가 아주 절묘한 $\lambda$를 잡아서, 구간이 정확히 $k$개 나오는 게 최적인 순간을 포착했다면 어떻게 될까? 이 경우, $DP[n] - \lambda k$ 가 $k$ 개의 구간으로 분할하는 최소 비용이 됨을 알 수 있다. 이렇게 운 좋은 $\lambda$ 를 찾을 수만 있다면 우리는 이 문제를 $O(n)$ 에 해결할 수 있으니, 이제 $\lambda$ 를 컨트롤함으로써 $k$ 개의 구간을 고르는 비용을 계산하는 접근을 시도하자.

그렇다면, 절묘한 $\lambda$를 항상 찾을 수 있을까? $k$ 는 $\lambda$ 가 증가하면 감소한다. 고로 최적 구간 개수가 $k$ 이하인지 초과인지로 이진 탐색을 하는 접근이 매력적으로 보인다. 하지만, 아쉽게도 이 정도 사실로는 문제를 해결하기 부족하다. 만약 $\lambda$를 증가시키면서 나온 구간의 개수가 $[10, 10, 10, 8, 8, 3, 3, 3, 1 \ldots]$ 와 같이 누락된 꼴로 나온다면, 구간이 2개 / 5개 / 9개 등일 때의 답을 알 수 없다. 예시로, $f(k) = (k$ 개의 구간을 사용했을 때의 최소 비용) 이라고 정의하자. $f(1) = 101, f(2) = 100, f(3) = 1$ 라고 하면, $k = 2$ 를 계산하는 적당한 $\lambda$ 를 찾을 수 없다.

하지만. 다행이도 이 예시 문제에 대해서는 저러한 걱정을 하지 않아도 된다. 이는 바로 $f(k)$ 가 볼록하기 때문이다. 즉, $f(k + 1) - f(k) \le f(k + 2) - f(k + 1)$ 를 만족한다.

Theorem 1. $DP[i][j] = Min_{k < j}(DP[i-1][k] + C[k+1][j])$ 와 같은 점화식에서, $C$ 배열이 Monge array라면, $DP[k][n] - DP[k+1][n] \ge DP[k+1][n] - DP[k+2][n]$ 이 성립한다.

이에 대한 증명은 아래에서 계속한다. 일단 이것이 사실이라고 생각하고, 문제를 해결해 보자. $(i, f(i))$ 를 점으로 하는 그래프를 그려보면, $y = x^2 + c$ 인 이차함수를 연상시키는, 아래로 볼록한 모양의 그래프가 그려진다. 이때 $f(i) + \lambda i$ 를 최소화하는 점은 $-\lambda$ 의 기울기로 접선을 그렸을 때 닿는 점과 동일하다는 것을 알 수 있다! 모든 점에 대해서 접선이 존재하니, 모든 $i$ 에 대해서도 $\lambda$ 를 찾을 수 있고, 고로 절묘한 $\lambda$ 가 항상 존재한다. 이 뿐만 아니라, 절묘한 $\lambda$ 를 이분 검색으로 찾을 수 있다. 위에서 관찰한 대로, $\lambda$ 가 커지면 $i$ 는 감소하고, 작아지면 $i$ 가 증가하는 경향성이 존재한다. 이는 그래프를 그려서 확인한 기하학적 관찰과도 일치한다. $\lambda$ 가 커지면 접선의 기울기가 아래쪽이니 왼쪽에 있는 점이 잡히고, 반대의 경우는 오른쪽에 있는 점이 잡힌다.

이제, $DP[k][n] + \lambda k$ 를 최소화하는 DP를 계산하고, 일반적으로 해를 역추적하는 요령을 사용하여 이 해에서 사용한 $k$가 얼마인지를 찾아주자. 이렇게 할 경우, 모든 기울기로 가능한 실수 $\lambda$ 에 대해서, 구간의 개수가 $k$ 이상/이하로 갈리는 나오는 첫 지점을 찾아주면, 절묘한 $\lambda$ 와 함께 답까지 찾아줄 수 있다.

하지만... DP에 실수 연산을 쓰는 것은 오차나 계산 효율성, 구현 등 여러 면에서 달갑지 않다. 실제로도 모든 가능한 기울기가 정수인 것이 자명하니, 정수 범위의 $\lambda$ 에서만 이분 탐색을 하는 것이 더 좋을 것 같다. 정수 범위의 $\lambda$ 에서만 이분 탐색을 한다고 문제가 생길까? 아쉽게도 다음과 같은 경우에 문제가 생긴다. $f(1), f(2), f(3), f(4), f(5), f(6) = [30, 20, 18, 16, 14, 14]$ 라고 하자. 그래프를 그려보면, $(f(2), 2), (f(3), 3), (f(4), 4), (f(5), 5)$ 와 같은 점들은 모두 한 직선 안에 있다. 이들에 대한 적절한 $\lambda$ 는 모두 공통적으로 $\lambda = 2$ 이다. 한편, $\lambda = 2$ 를 대입한 후 DP를 구해서 역추적하면, 구간의 개수가 ${2, 3, 4, 5}$ 중 어떤 것이 나올 지 모른다! (이러한 것 중 최솟값이 나오도록 컨트롤할 수 있는 경우도 있으나, 예를 들어 Convex hull trick을 사용한다면 컨트롤이 매우 힘들 것이다.) 만약 $k = 3$ 인데 구간의 개수가 2로 나온다면, $\lambda \ge 2$ 에서는 구간 개수가 $k$ 미만, 아니면 $k$ 초과인 상황이 된다. $k = 3$ 인데 구간의 개수가 5로 나온다면, $\lambda \geq 1$ 에서는 구간 개수가 $k$ 미만, 아니면 $k$ 초과가 된다. 위 경우, 실제 $k$ 에 맞는 $\lambda$ 가 1인지 2인지를 알 수 있는 좋은 방법이 없다.

두 문제 사이에서 절충하는 좋은 방법은 반정수 범위에서 이분 탐색 을 하는 것이다. $n + 0.5$ 와 같은 반정수는 접하는 점이 하나밖에 없기 때문에, DP의 결과물로 나올 수 있는 답이 모호하지 않고 정확히 하나로 결정되어 있다. 고로, 구간의 개수가 $k$ 이상/이하로 갈리는 첫 반정수 지점 은 모호하지 않게 찾을 수 있고, 이렇게 이분 탐색을 변형할 경우 $\lambda$ 는 단순히 갈리는 반정수 지점 사이로 선택하면 된다. 반정수를 직접 구현할 필요는 없고, 그냥 $C[i][j]$ 함수의 반환 값을 2배로 조정하면, 초기 $\lambda$ 를 찾는 이분 탐색은 홀수 ($2n+1$) 에서, 이후 $\lambda$ 를 찾은 이후에는 짝수 ($2\lambda$) 에서 DP를 구하면 된다.

이제 Theorem 1을 증명한다.

Theorem 1의 증명

Preliminaries. 이러한 문제는 특정 DAG에서의 최단 경로를 찾는 문제라고 생각할 수 있다: 모든 $0 \le i < j\le N$ 에 대해, $i \rightarrow j$ 로 가는 간선의 가중치가 $C[i + 1][j]$ 일 때, $0$ 번 정점에서 $N$번 정점으로 가는 간선의 개수가 $k$ 인 최단 경로를 찾는 것이다. 고로 이후 이 문제를 설명할 때는 최단 경로 를 찾는다는 맥락에서 서술한다.

Definition 1. 두 간선 $(i_1, j_1)$ 과 $(i_2, j_2)$ 에 대해서 $i_1 \leq i_2 < j_2 \leq j_1$을 만족한다면, $(i_1, j_1)$ 은 $(i_2, j_2)$를 포함한다.

Definition 2. 경로 $P_1 = {0, \ldots, i_1, j_1, \ldots, N}$ 과 $P_2 = {0, \ldots, i_2, j_2, \ldots, N}$ 에 대해서, 만약 $(i_1, j_1)$이 $(i_2, j_2)$를 포함한다면, 경로 교환 이라는 연산을 통해서 두 올바른 경로 $Q_1 = {0, \ldots, i_1, j_2, \ldots, N}$과 $Q_2 = {0, \ldots, i_2, j_1, \ldots, N}$을 만들 수 있다.

Lemma 1. $w(P)$ 를 경로의 가중치 합이라 하자. $P_1, P_2$에 경로 교환을 적용한 것을 $Q_1, Q_2$라 했을 때, $w(Q_1) + w(Q_2) \leq w(P_1) + w(P_2)$ 이다.

Proof of Lemma 1. $w(Q_1) + w(Q_2) = w(P_1) + w(P_2) - C[i_1 + 1][j_1] - C[i_2 + 1][j_2] + C[i_1+1][j_2] + C[i_2 + 1][j_1]$ 이다. $i_1 + 1 \le i_2 + 1 \le j_2 \le j_1$ 이다. 고로 Monge property에 따라 부등식이 성립한다.

Lemma 1에 의해, 경로 교환을 마음대로 적용해도, 두 경로의 길이의 합을 늘리지 않음을 확인할 수 있다.

Lemma 2. 어떠한 $1 \leq a \leq b \leq n$ 에 대해서, $P_1, P_2$가 각각 0번 정점과 $a$번, $b$번 정점을 잇는 서로 다른 두 경로라 하자. 이 때, $P_1$의 간선 수는 $k_1$, $P_2$의 간선 수는 $k_2$며, $k_1 \geq k_2$를 만족한다면, 임의의 $0 \leq x \leq k_1 - k_2$에 대해 다음 두 조건을 만족하는 $e_1 = (i_1, j_1) \in P_1, e_2 = (i_2, j_2) \in P_2$ 가 존재한다:

• $e_2$가 $e_1$을 포함한다.
• $i_1$에서 끝나는 $P_1$의 prefix가 $i_2$에서 끝나는 $P_2$의 prefix보다 $x$개 더 많은 간선을 가진다.

Proof of Lemma 2. $(k_1, k_2)$ 의 pair에 대해서 수학적 귀납법을 사용한다. 즉 $P_1$의 길이가 $k_1$보다 작거나, $P_1$의 길이가 $k_1$이며 $P_2$의 길이가 $k_2$보다 작은 경우 항상 명제가 성립한다고 보는 것이다. 기저 조건은 $k_1 = k_2 = 1$으로 이 때는 자명하다. 세 가지 케이스가 있다.

• Case 1 : $k_2 = 1$. $e_2$를 $P_2$의 유일한 에지라 하자. $P_1$의 어떤 에지를 가져와도 $e_2$에 포함된다. 고로 $e_1$을 $P_1$의 $x+1$번째 에지로 두면 그러한 두 간선을 찾을 수 있다.
• Case 2 : $k_1 \geq k_2 \geq 2$이며, $P_2$의 마지막 에지가 $P_1$의 마지막 에지를 포함하지 않는다. $P_1$의 마지막 에지를 $(f_1, a)$, $P_2$의 마지막 에지를 $(f_2, b)$ 라 두면, 가정에 의해 $a \leq b$이니 $f_1 < f_2$ 이다. $P_1$과 $P_2$에서 마지막 에지를 제거하면 $f_1 < f_2$, $k_1 - 1 \geq k_2 - 1$고, 임의의 $0 \leq x \leq (k_1 - 1) - (k_2 - 1)$에 대해 답을 찾고 싶은 것이니 귀납 가정을 사용할 수 있다.
• Case 3 : $k_1 \geq k_2 \geq 2$이며, $P_2$의 마지막 에지가 $P_1$의 맨 뒤 $y > 0$개 에지를 포함한다. $P_2$의 마지막 에지를 $e_2$라 두면, $e_1$은 $P_1$의 $k_2 + x$번째 에지이며 $e_2$에 포함되어야 한다. 즉, $k_2 + x \geq k_1 - y + 1$일 경우 $e_2$를 마지막 에지라 둘 수 있다. 식을 더 정리하면 $y \geq k_1 - k_2 - x + 1$일 때 즉시 두 간선을 찾을 수 있다.
• $y \leq k_1 - k_2 - x$ 일 경우, $P_1$에서 $y$개의 에지를 제거하면, $P_1$의 끝점이 $P_2$의 끝점보다 작고, $k_1 - y \geq k_2$이다 ($x \geq 0$). 귀납 가정에 의해서 임의의 $0 \leq x \leq (k_1 - k_2 - y)$ 에 대해 답을 찾을 수 있다.

Proof of Theorem 1. $P_1$을 간선 수가 $K+1$인 가중치 최소의 경로, $P_2$를 간선 수가 $K-1$인 가중치 최소의 경로라 하자. Lemma 2에 의해서, $e_2$가 $e_1$을 포함하며, $i_1$에서 끝나는 $P_1$의 prefix가 $i_2$에서 끝나는 $P_2$의 prefix보다 1개 더 많은 간선을 가지는 $e_1 \in P_1, e_2 \in P_2$를 찾을 수 있다. 이들 간에 경로 교환을 수행하면, 간선 수가 $K$인 두 경로 $Q_1, Q_2$를 찾을 수 있으며, 이 때 $w(Q_1) + w(Q_2) \leq w(P_1) + w(P_2)$ 를 만족한다. 고로 $f(K) + f(K) \leq w(Q_1) + w(Q_2) \leq w(P_1) + w(P_2) = f(K-1) + f(K+1)$이고, Theorem 1이 성립한다.

역추적하기

기본적으로 알고리즘 자체가 역추적하는 루틴을 가정하니, 실제 답을 복원하는 것 역시 간단하다고 생각할 수 있다. 하지만 잘 들여다보면 그렇지 않다. 위에서 언급한, $f(1), f(2), f(3), f(4), f(5), f(6) = [30, 20, 18, 16, 14, 14]$ 와 같은 경우를 다시 살펴보자. 반정수를 사용하는 트릭을 통해서 2, 5 개의 파티션을 사용하는 해는 찾을 수 있다. 하지만 3개나 4개의 파티션을 사용하는 해를 찾을 수 있다는 보장은 할 수가 없다. 이러한 경우에는 어떻게 해야 할까? Theorem 1을 증명하기 위해 사용한 Lemma 2를 다시 돌아보자:

Lemma 2. 어떠한 $1 \leq a \leq b \leq n$ 에 대해서, $P_1, P_2$가 각각 0번 정점과 $a$번, $b$번 정점을 잇는 서로 다른 두 경로라 하자. 이 때, $P_1$의 간선 수는 $k_1$, $P_2$의 간선 수는 $k_2$며, $k_1 \geq k_2$를 만족한다면, 임의의 $0 \leq x \leq k_2 - k_1$에 대해 다음 두 조건을 만족하는 $e_1 = (i_1, j_1) \in P_1, e_2 = (i_2, j_2) \in P_2$ 가 존재한다:

• $e_2$가 $e_1$을 포함한다.
• $i_1$에서 끝나는 $P_1$의 prefix가 $i_2$에서 끝나는 $P_2$의 prefix보다 $x$개 더 많은 간선을 가진다.

이 Lemma를 사용하여 역추적을 해 보자. 만약 주어진 $k$ 가 항상 답을 찾을 수 있는 위치에 있다면 (즉 반정수로 찾아지는 분할이라면) 역추적은 자명하다. 반정수를 사용하는 트릭을 통해, $k_1, k_2$ 개의 파티션을 사용하는 분할을 찾자. 이 때 $k_2 < k < k_1$ 를 만족한다. Lemma 2에서, 이 분할들은 모두 $a = b = n$ 번 정점을 잇는 두 경로 $P_1, P_2$ 에 대응된다고 볼 수 있다. 이제 $x = k - k_2$ 라고 두면, $i_1$ 에서 끝나는 $P_1$ 의 prefix가 $i_2$ 에 끝나는 $P_2$ 의 prefix보다 $k - k_2$ 개 더 많은 간선을 가지는 $e_1 = (i_1, j_1) \in P_1, e_2 = (i_2, j_2) \in P_2$ 이 존재한다. (실제 이 간선을 찾는 것은, 포함되는 쪽의 간선을 고정시킨 후 Two pointers나 이분 탐색을 사용하면 된다). 이 두 간선 $e_1, e_2$ 에 대해서 경로 교환을 실시한다면, $Q_1$ 은 $P_2$ 보다 $k - k_2$ 개 더 많은 간선을 가지는 최적해가 된다. 고로 $k$ 개의 간선을 가지는 $Q_1$ 을 찾아줄 수 있다. 이러한 방식으로, 아래 연습문제 2개를 풀 수 있다.

$\lambda$ 가 항상 존재하는 다른 예시

위와 같이 Monge array가 아니더라도, Min-cost Max-flow와 같은 Augmenting path 알고리즘들은 비슷한 볼록성을 띈다. 작동 과정에서 보통 각 augmenting path의 길이가 단조증가/감소하기 때문이다. Min-cost Max-flow 외에도 Weighted General Matching, Weighted Matroid Intersection도 augmenting path를 사용한다. 이것이 함의하는 사실은 다음과 같다. 예를 들어서 어떠한 문제를 DP로도 해결할 수 있고 Min-cost Max-flow로도 해결할 수 있다면, Min-cost Max-flow로 해결할 수 있다는 그 사실 자체가 볼록성의 증명(!) 이 된다. 고로, Min-cost Max-flow 모델링을 생각했다면, 그것을 구현할 필요도 없이, 그대로 증명으로 사용한 후 Aliens trick을 사용하면 된다. 이와 같은 방법으로 해결할 수 있는 문제가 연습 문제 중 존재한다.

또한, 이러한 식으로 $\lambda$ 라는 추가적인 인자를 잡아서 다른 인자를 조종하는 기법은 새로운 방법이 아니며, 수학에서 사용하는 라그랑주 승수법과 굉장히 비슷한 형태를 띈다. 고로, DP 문제를 해결하지 않더라도, 또한 꼭 $\lambda$ 를 어떠한 파티션의 개수에 적용하지 않더라도 비슷한 방법의 문제 해결 방법을 적용할 여지는 충분히 있다. 이러한 문제들의 예시로는 , NAIPC 2017. Blazing New Trails 를 참고하라. 이 문제는 Aliens trick을 사용하지는 않으나, $\lambda$ 라는 추가적인 인자를 조종하는 방식으로 문제를 해결하는 점에서 Aliens trick과 비슷하다고 볼 수 있다.

Practice problem

• IOI 2016: Aliens
• APIO 2014: Split the Sequence (Solve this in $O(N\log N)$!)
• GP of Korea 2018/2019. Utilitarianism
• Romanian IOI 2017 Selection. Popcorn
• 서울대학교 2019. 꽃집 (Same as problem in Chapter 3)
• Ptz Winter 2019. 300iq Contest 1: Jealous Split

6. Slope Trick

흔히 "Slope Trick" 이라고 불리는 이 방법은 여기서 설명할 다른 DP 최적화와는 상당히 다르다. 위의 DP 최적화는 명확히 정해진 형태의 공식을 최적화한다면, Slope Trick에서는 최적화할 수 있는 DP 식이 정해지지 않았기 때문에 다양한 형태의 DP 점화식을 최적화할 수 있다. 또한 최적화하는 방법이 항상 같지 않아서, 어떠한 점화식이 Slope Trick으로 풀리는 지도 쉽게 알기 힘들 수 있고, 모델링 방법에 따라서 풀이의 복잡도가 매우 달라질 수 있다. 일반적으로 Slope Trick은 $DP[i][]$ 라는 함수가 볼록 함수 라고 가정하고, 이 함수에 하는 연산이 볼록 함수, 혹은 이것의 도함수에 대한 간단한 연산일 경우 적용할 수 있다.

정확히 이 방법이 무엇인지에 대해서는 [Tutorial] Slope Trick 에 매우 잘 나와있으니, 해당 글을 읽고 대략 어떠한 류의 문제들을 최적화하는지 살펴보는 것이 좋을 것이다.

여담으로, Slope Trick으로 풀리는 문제들의 경우 대부분 Min-cost Max-flow로 모델링 가능한 문제들과 궁합이 상당히 잘 맞는다. Slope Trick에서 관리하고 있는 함수가 볼록이라는 사실, 그리고 MCMF의 augmenting path의 길이가 단조증가한다는 사실이 어느 정도 공통점을 주는 거 같은데, 이 부분에 대해서는 관심이 있다면 연구를 해 보는 것도 좋을 것 같다.

Practice problems

• Codeforces. Sonya and Problem Wihtout a Legend ($N\log N$ 에 해결해 보자.)
• Codeforces. Buy Low Sell High
• KAIST 2018 Spring. Touch The Sky
• Singapore National OI 2018. Safety
• (AtCoder) KUPC 2016. Wall
• GP of Korea 2019/2020. Parklife
• JAG Autumn 2017. Farm Village
• Codeforces. Moving Walkways
• APIO 2016. Fireworks
• Codeforces. Mateusz and Escape room (Challenge problem!)
• World Finals 2018. Conquer The World (Challenge problem!)
• GP of Kazan 2019/2020. Honorable Mention (Challenge problem!)

7. Hirschburg's Algorithm

• Recurrence: $DP[i][j] = min(DP[i-1][j], DP[i][j-1]) + C[i][j]$ (와 같은 류의 점화식)
• Condition: None
• Naive Complexity: $O(nm)$ memory usage for tracking optimal answer
• Optimized Complexity: $O(n + m)$ memory usage for tracking optimal answer

Hirschburg's algorithm은 대회에 많이 출제되거나 유용한 알고리즘은 아니다. 시간 복잡도를 최적화하는 것이 아니라 공간 복잡도를 최적화하기 때문이다. 하지만 알고리즘이 사용하는 관찰은 상당히 흥미롭고, LCS(Longest common subsequence)라는 매우 영향력있는 문제를 현실에서 해결하는 데는 매우 유용하게 사용되기 때문에 그 자체로 배워볼 가치가 있는 알고리즘이다.

LCS는 위와 비슷한 점화식을 통해서 $O(nm)$ 시간/공간 복잡도에 해결할 수 있는 것이 잘 알려져 있다. 또한, $DP[i], DP[i-1]$ 열만 가지고 있는 식으로 공간 복잡도를 $O(m)$ 으로 줄이는 토글링 이라는 기법 역시 잘 알려져 있다. 하지만, 만약에 답을 역추적해야 한다고 하면 토글링을 사용할 수 없다. 답을 역추적하기 위해서는 DP 표 전부, 혹은 경로가 향하는 방향을 저장하는 역추적 표 전부를 가지고 있어야 하기 때문이다.

Hirschburg's algorithm은 이 문제를 해결하기 위해 분할 정복 을 사용한다. 이 과정에서 DP 테이블을 사이클이 없는 평면 그래프 (Planar DAG) 로 보는 것이 상당히 중요하다. $n \times m$ 격자의 각 모서리에 정점 $(i, j)$ 가 있고, 가로, 세로, 그리고 대각선으로 방향성 간선이 있는 그래프를 생각해 보자. 이러한 간선들은 각각 $(i-1, j), (i, j-1), (i-1, j-1)$ 에서 받아오는 상태 전이에 대응된다. 각 간선 (혹은 정점) 에는 적절한 가중치가 적혀있을 것이고, 이 때 DP의 최솟값을 구하는 것은 위와 같은 그래프에서 $(0, 0) \rightarrow (n, m)$ 으로 가는 최단 경로 를 구하는 것과 동일하다. 사이클이 없는 그래프이기 때문에 최장 경로 역시 최단 경로와 똑같은 방법으로 구할 수 있다.

이제 이러한 격자에 대해서 분할정복을 하자. $(0, m/2), (1, m/2), \ldots (n, m/2)$ 에 대해서, $(0, 0)$ 에서 해당 점으로 가는 최단 경로, 해당 점에서 $(n, m)$ 으로 가는 최단 경로를 모두 $O(nm)$ 시간, $O(n)$ 공간을 사용하여 토글링+DP로 계산해 줄 수 있다. 이는 문자열 하나를 반으로 나눈 후, 양쪽 반에 대해서 다른 문자열과 LCS를 구해주는 것과 동일하게 생각하면 된다. 자명하게 알 수 있는 사실은, 최단 경로는 $(i, m/2)$ 중 하나의 점을 지난다는 것이다. 이 점들이 격자를 분리하기 때문이다 (separator). 모든 점 $i$ 에 대해서 해당 점을 지나는 최단 경로가 있는지는, 위에서 계산한 DP 결과의 합이 최솟값인지 아닌지를 토대로 쉽게 판정할 수 있다.

이렇게 최단 경로 중 하나가 지나는 점의 위치를 $(x, m/2)$ 라고 하자. 이제 $(0, 0) \rightarrow (x, m/2)$ 로 가는 최단 경로, $(x, m/2) \rightarrow (n, m)$ 로 가는 최단 경로를 재귀적으로 구한 후, 이 둘을 단순히 이어주면 역추적을 할 수 있다. 이 방법을 사용하면, 탐색하는 격자의 후보가 매번 반으로 줄기 때문에, $O(nm + nm/2 + nm/4 + \ldots ) = O(nm)$ 의 시간 복잡도를 가진다. 또한 재귀 호출이 사용하는 공간 복잡도가 $O(\log m)$ 밖에 안 되기 때문에, 공간 복잡도는 토글링에 필요한 $O(m)$, 그리고 답 저장에 필요한 $O(n)$ 정도에 지배된다. 알고리즘 자체로는 중요하지 않지만, 신선한 문제 해결 기법이니 알아 두는 것을 추천한다. 이후 논의하게 될 Circular LCS에서도 평면성을 활용한 비슷한 접근법을 자주 활용하게 될 것이다.

Practice problems

• CSAcademy: Classic Task
• Codeforces. Candies and Stones
• BOJ 17161: 편집 거리 (Hard)
• BOJ 18438: LCS 5

다른 글 보기

​
Part 1 (Convex Hull, D&C, Monotone Queue)
​
Part 2 (Knuth, Lagrange, Slope, Hirschberg)
​
Part 3 (Circular LCS)
​
Part 4 (Dynamic Tree DP)