이 글에서는 다이나믹 프로그래밍에 대한 분할 정복 최적화 를 다루고자 한다.
참고 : Koosaga - 동적 계획법 최적화. 무려 9가지의 DP 최적화 방식을 망라해서 다루고 있고, 전체적인 기법에 대한 깊은 insight가 묻어나는 글이다. 갈길이 너무나 멀다는걸 체감하게 한다…

Motivation

다음과 같은 형태의 점화식을 생각하자. 여기서 $k$는 1부터 $K$까지, $i$ 는 $N$ 까지 채워야 한다고 하자. \(DP(k, i) = \min_{j < i} (DP(k-1, j) + C(j, i))\) 이 DP에서 총 계산해야 할 칸은 $NK$칸이고, 한 칸을 계산하기 위해 $N$개의 min을 구해야 하므로 수행 시간은 $O(N^2 K)$ 임을 쉽게 알 수 있다. 우리의 목표는 이 문제를 보다 빠르게 해결하는 방법을 찾는 것이다.

Conditions

추가적인 조건이 없다면, 시간 복잡도를 줄이기는 쉽지 않아 보인다. 그래서, 다음과 같은 추가 조건을 만족하는 경우의 DP 문제만 생각할 것이다.

  1. 답이 되는 j 라는 개념을 생각하자. 위 점화식에서 실제로 DP(k, i) 를 만들어내는 j가 있을 것이다. 여러 개의 j가 min이 되는 경우, 그러한 j 중 첫 번째를 i번째에 대해 답이 되는 j, 즉 $j_i$ 라고 부를 것이다. 즉, 다음 조건을 만족한다. \(DP(k, i) = DP(k-1, j_i) + C(j_i, i)\)
  2. 우리는, 답이 되는 j가 단조증가하는 DP만 생각할 것이다. 즉, $i_1 < i_2$에 대해, $j_{i_1} \leq j_{i_2}$를 만족하는 DP를 생각한다.

Idea

단조증가라는 2번 조건에서, 우리는 뭔가를 이분 탐색 하겠다는 아이디어를 얻을 수 있다.

어떤 $m$ 에 대해 $DP(k, m)$ 을 알고 있다면, $i > m$ 일 때 $DP(k, i)$ 를 구하는 과정에서 $\min_{j_m \leq j < i}$ 로 봐야하는 $j$의 칸수를 줄여낼 수 있기 때문이다.

구체적으로, 우리가 DP(k, s..e) 을 구하는 상황을 다음과 같은 순서로 진행할 수 있다.

  1. $m = (s + e) / 2$ 에 대해, $DP(k, m)$을 구한다. 이때, $j_m$ 을 구하게 되고, 이 한 번 구하는 과정은 $O(N)$ 시간이 소요된다.
  2. 이제, DP(k, s..m-1)와 DP(k, m+1..e) 을 각각 재귀적으로 호출하되, 각 재귀 호출에서 이 구간을 위해 봐야 하는 $j$의 범위를 들고다니면서 관리하면 된다.

Time Complexity

2번 과정에서, 재귀 트리의 다음 레벨에서 직접 구하는 DP값은 2개가 된다. 그러나, 봐야 하는 $j$의 구간이 양쪽으로 갈려서 한 $j$값을 많아야 두 번씩만 (경계값은 2번, 나머지는 한 번) 확인하기 때문에, $O(N)$ 시간에 2개를 구하는 셈이 된다. 그 다음 재귀는 4조각으로 전체 구간을 나누고, $j$값도 4조각으로 나누어 확인하고 있으므로, $O(N)$ 시간에 4개를 구하는 셈이 된다. 재귀 트리의 높이가 $O(\log N)$ 임이 자명하므로, 전체 DP(k, 1..n) 을 구하는 데 쓰는 시간은 $O(N \log N)$ 이고, 각각의 $K$에 대해 이를 수행하더라도 소요 시간은 $O(NK \log N)$ 이다.

Monge Array

답이 되는 $j$의 단조성을 보이는 것은 쉽지 않다. 어떤 경우에는 직접 이 부분을 증명하는 것이 더 쉬울 때도 있는데, 문제 상황에 의해 쉽게 insight를 얻을 수 있는 경우에는 믿음을 가지면 되고(…) 그렇지 않은 경우에는 아래 명제가 유용하다.

Theorem $C(j, i)$ 가 Monge Array 이면, 즉 임의의 $a \leq b \leq c \leq d$ 에 대해, \(C(a, c) + C(b, d) ≤ C(a, d) + C(b, c\) 이면 $j$의 단조성이 성립한다.

Proof $C$가 Monge array 라고 하자. 이떄, $p < q$ 이지만 $j_{p} > j_{q}$ 라면, \(DP(k, p) = DP(k-1, j_p) + C(j_p, p) < DP(k-1, j_q) + C(j_q, p)\) \(DP(k, q) = DP(k-1, j_q) + C(j_q, q) \leq DP(k-1, j_p) + C(j_p, q)\) 이러한 식이 성립한다. 첫번째 식에 등호가 성립하지 않는 것은, $j_p, j_q$의 정의를 최소값이 되는 최소의 $j$로 정하였기 떄문에, 두번째 식에서는 어차피 $j_p$ 가 더 크므로 두 값이 같아도 $j_q$ 의 정의를 위배하지 않지만 첫번째 식에서는 등호가 성립한다면 $j_p$의 정의에 어긋나기 때문이다.

위 두 식의 양변을 각각 더하여, 다음을 얻는다. \(C(j_p, p) + C(j_q, q) < C(j_q, p) + C(j_p, q)\) 그런데, 우리는 $j_q < j_p < p < q$ 임을 알고 있으므로, Monge array의 정의에 의해 \(C(j_q, p) + C(j_p, q) \leq C(j_p, p) + C(j_q, q)\) 여야 한다. 이 두 식이 모순이므로, $j$의 단조성이 증명되었다.