Divide and Conquer Optimization

작성일 | In

서론

Divide and Conquer Optimization은 점화식이 아래 조건을 만족할 때 사용할 수 있습니다.

  • 점화식 꼴 : $\displaystyle D(t, i) = min_{1 ≤ j < n}{D(t-1, j)+C(j, i)}$
  • 조건 : $D(t, i) = D(t-1, j) + C(j, i)$을 만족하는 가장 작은 $j$를 $P(t, i)$이라고 할 때 $P(t, i) ≤ P(t, i+1)$을 만족

Naive하게 계산하면 $D(t, 1 \dots N)$를 계산할 때 $O(N^2)$ 시간이 걸리므로 총 $O(KN^2)$이 걸리지만(K = 가능한 t의 개수), 위 조건을 만족하면 분할 정복을 이용해 $O(KN\log N)$에 계산할 수 있습니다.

설명

$i \in [s, e]$인 i에 대해 $D(t, i)$를 계산한다고 해봅시다.
$D(t-1, \ast)$를 알고 있으면 $[s, e]$의 중점 $m(=(s+e)/2)$에 대해 $D(t, m)$은 $O(N)$에 계산해줄 수 있고, 동시에 $P(t, m)$도 구할 수 있습니다.
$P(t, i) ≤ P(t, i+1)$이 성립하기 때문에 $i \in [s, m-1]$인 i에 대해 $D(t, i)$를 계산할 때는 탐색하는 $j$의 범위를 $P(t, m)$ 이하로 제한해도 되고, $i \in [m+1, e]$인 $i$에 대해 $D(t, i)$를 계산할 때는 탐색하는 $j$의 범위를 $P(t, m)$ 이상으로 제한해도 됩니다.

DP를 계산하는 것은 재귀 함수로 간단하게 구현할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
//D[t][s...e]를 구해야 하고, j의 탐색 범위는 [l, r]
void f(int t, int s, int e, int l, int r){
  if(s > e) return;
  int m = s + e >> 1;
  int opt = l;
  for(int i=l; i<=r; i++){
    if(D[t-1][opt] + C[opt][m] > D[t-1][i] + C[i][m]) opt = i;
  }
  D[t][m] = D[t-1][opt] + C[opt][m];
  f(t, s, m-1, l, opt);
  f(t, m+1, e, opt, r);
}

특수한 경우

추가로, 점화식의 $C(j, i)$가 monge array이면 $P(t, i) ≤ P(t, i+1)$를 만족합니다. ($a ≤ b ≤ c ≤ d$일 때 $C[a, c] + C[b, d] ≤ C[a, d] + C[b, c]$) monge array의 성질로 증명할 수 있습니다.
$C’[i, j] = D[t-1, i-1] + C[i, j]$라고 하면 $C’$도 monge array인 것을 알 수 있습니다. 이 글에 나와있는 3번 성질에 의해 $P(t, i) ≤ P(t, i+1)$인 것을 알 수 있습니다.

수정 기록

  • 2020.04.30 - 글을 완전히 갈아엎음