Divide & Conquer Optimization

Divide & Conquer Optimization은 특정 조건을 만족할 때 활용할 수 있는 최적화 기법이다. 주로 Dynamic Programming에서 쓰인다고 생각할 수 있으나, Dynamic Programming이 아닌 상황에서도 널리 쓰일 수 있다.

조건 1) DP 점화식 꼴

$D[t][i] = \min_{k < i}(D[t-1][k] + C[k][i])$와 같이 $D[t][i]$ 안에 $D[t-1][k]$와 $k$에 대한 함수 $f(k)$가 들어가 있는 경우

조건 2) $A[t][i]$는 $D[t][i]$를 만족시키는 최소 $k$라 할 때 아래 부등식을 만족

$A[t][i] \leq A[t][i+1]$

위 두 조건을 만족하면 원래 $O(KN^2)$의 시간복잡도를 갖는 DP를 Divide & Conquer를 통해 $O(KN \lg N)$에 해결 할 수 있다. 여기서 $K$는 단계 수(가능한 $t$의 종류)를 의미한다.

Divide & Conquer(분할정복)을 이용해 이를 한 단계 마다 $O(N \lg N)$ 시간안에 해결하는 방법은 다음과 같다.

void do_dp(int t, int s, int e, int p, int q) { // D[t][s], D[t][s+1], ..., D[t][e]를 계산하는 함수. // (여기서 가능한 k의 범위는 p~q 사이) if (s > e) return; int m = (s+e) >> 1; // 1. D[t][m]에 대해 가능한 답을 선형 시간에 계산 D[t][m] = 2e9; for (int k=p;k<=q&&k<m;k++){ int v = D[t-1][k] + C[k][m]; if (D[t][m] > v) D[t][m] = v, K[t][m] = k; } // 2. D[t][s], ..., D[t][m-1]에 대해서 계산하기 위한 재귀 호출 do_dp(t, s, m-1, p, K[t][m]); // 3. D[t][m+1], ..., D[t][e]에 대해서 계산하기 위한 재귀 호출 do_dp(t, m+1, e, K[t][m], q); // 2, 3에 대해 가능한 k의 후보는 조건에 의해 줄어든다. }

여기서 단계별로 시간복잡도가 $O(N \lg N)$이라는 것을 보이기 위해, 11번째 줄에 있는 for문이 돌아가는 횟수를 생각해보자. for문이 돌아가는 횟수가 $N \lg N$에 비례하다는 것을 어렵지 않게 보일 수 있다.

단계 수 $K=1$인 경우도 종종 있는데, 이 때 점화식을 조건 1 꼴로 쓸 수는 있지만 Dynamic Programming이 아니라고 볼 수 있다. $K=1$인 경우 이를 이용하여 해결하는 문제는 대표적으로 IOI 2014 Holiday, BOJ 11001번 김치, ICPC WF2016 B번 문제가 있다.

이를 이용해 해결할 수 있는 다른 문제로는 ICPC WF 2016 B번 문제가 있다.

조건 2를 만족하는 특수한 경우들

1) Quadrangle Inequalty (사각부등식) 만족하는 경우

조건 1의 예시 점화식과 같은 꼴이고, 비용 $C$가 $a \leq b \leq c \leq d$인 $a$, $b$, $c$, $d$에 대해 사각부등식 $C[a][c] + C[b][d] \leq C[a][d] + C[b][c]$를 만족하는 경우 조건 2도 만족한다.

---

명제) $D[t][i] = \min_{k < i}(D[t-1][k] + C[k][i])$이고, $C[a][c] + C[b][d] \leq C[a][d] + C[b][c]$ 일 때, $A[t][i] \leq A[t][i+1]$이다.

귀류법으로 증명할 수 있다.

어떤 $i$에 대해 $A[t][i] = j > A[t][i+1] = k$라고 하자.

$D[t][i] = D[t-1][j] + C[j][i] < D[t-1][k] + C[k][i]$ 이고, $D[t][i+1] = D[t-1][k] + C[k][i+1] \leq D[t-1][j] + C[j][i+1]$ 이다.

여기서,

$C[k][i+1] - C[j][i+1] \leq D[t-1][j] - D[t-1][k] < C[k][i] - C[j][i]$ 이므로,

$C[k][i+1] - C[j][i+1] < C[k][i] - C[j][i]$,

즉, $C[k][i+1] + C[j][i] < C[k][i] + C[j][i+1]$ 이다. ($k < j < i < i+1$)

이 때, 사각부등식을 만족한다는 가정에 모순되므로 위 명제는 참이 된다.

---