콘텐츠로 이동

분할 정복 DP

분할 정복은 동적 계획법 최적화 기법입니다.

전제 조건

일부 동적 계획법 문제는 다음과 같은 형태의 점화식을 가집니다.

$$ dp(i, j) = \min_{0 \leq k \leq j} \\{ dp(i - 1, k - 1) + C(k, j) \\} $$

여기서 $C(k, j)$는 비용 함수이며, $j \lt 0$일 때 $dp(i, j) = 0$입니다.

$0 \leq i \lt m$이고 $0 \leq j \lt n$이며, $C$를 계산하는 데 $O(1)$ 시간이 걸린다고 합시다. 그러면 위 점화식을 그대로 계산하면 $O(m n^2)$이 걸립니다. 상태가 $m \times n$개 있고, 각 상태마다 전이가 $n$개 있습니다.

위 식을 최소화하는 $k$의 값을 $opt(i, j)$라고 합시다. 비용 함수가 사각 부등식을 만족한다고 가정하면, 모든 $i, j$에 대해 $opt(i, j) \leq opt(i, j + 1)$임을 보일 수 있습니다. 이를 단조성 조건이라고 합니다. 그러면 분할 정복 DP를 적용할 수 있습니다. 고정된 $i$에 대해 최적의 "분할 지점"은 $j$가 증가함에 따라 증가합니다.

이를 이용하면 모든 상태를 더 효율적으로 계산할 수 있습니다. 어떤 고정된 $i$와 $j$에 대해 $opt(i, j)$를 계산했다고 합시다. 그러면 임의의 $j' < j$에 대해 $opt(i, j') \leq opt(i, j)$임을 알 수 있습니다. 즉, $opt(i, j')$를 계산할 때 고려해야 할 분할 지점이 그만큼 줄어듭니다!

실행 시간을 최소화하기 위해 분할 정복의 아이디어를 적용합니다. 먼저 $opt(i, n / 2)$를 계산합니다. 그다음, $opt(i, n / 2)$ 이하임을 알고 있는 상태에서 $opt(i, n / 4)$를 계산하고, $opt(i, n / 2)$ 이상임을 알고 있는 상태에서 $opt(i, 3 n / 4)$를 계산합니다. $opt$의 하한과 상한을 재귀적으로 추적하면 $O(m n \log n)$의 실행 시간을 얻습니다. 구현 세부 사항은 아래 코드를 참고하십시오.

분할 정복의 복잡도를 증명하기 위해, 먼저 재귀에 $O(\log{n})$개의 레벨이 있다는 점에 주목하십시오. 각 레벨에서 $O(n)$번의 단계가 수행된다고 주장합니다. $k$번째 레벨에서 $\text{opt}$ 구간들(코드에서 $optl$과 $optr$로 표기됨)의 길이 합을 $S_k$라고 하고, 레벨 $k$에서 길이가 $x$인 구간이 분할될 때마다 그 결과로 생기는 구간(들)의 길이 합은 최대 $x + 1$임을 관찰하십시오. 또한 레벨 $k$에서는 최대 $2^k$번의 분할이 수행되므로, $S_{k + 1} \leq S_k + 2^k$가 성립합니다. $S_0 = n$으로 두고 이 상한을 귀납적으로 적용하면, 각 레벨 $k$에 대해 다음을 얻습니다.

$$ S_k < n + 2^k \in O(n). $$

따라서 각 분할 정복의 복잡도는 $O(n\log{n})$이고, 전체 DP 계산의 복잡도는 $O(mn\log{n})$입니다.

일반적인 구현

구현은 문제에 따라 다르지만, 꽤 일반적인 템플릿은 다음과 같습니다. 함수 compute는 이전 행 $i-1$의 상태 dp_before가 주어졌을 때 한 행 $i$의 상태 dp_cur를 계산합니다. 이 함수는 compute(0, n-1, 0, n-1)로 호출해야 합니다. 함수 solve는 m개의 행을 계산하고 결과를 반환합니다.

int m, n;
vector<long long> dp_before, dp_cur;

long long C(int i, int j);

// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    pair<long long, int> best = {LLONG_MAX, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k});
    }

    dp_cur[mid] = best.first;
    int opt = best.second;

    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

long long solve() {
    dp_before.assign(n,0);
    dp_cur.assign(n,0);

    for (int i = 0; i < n; i++)
        dp_before[i] = C(0, i);

    for (int i = 1; i < m; i++) {
        compute(0, n - 1, 0, n - 1);
        dp_before = dp_cur;
    }

    return dp_before[n - 1];
}

주의할 점

분할 정복 DP 문제에서 가장 어려운 부분은 $opt$의 단조성을 증명하는 것입니다. 이것이 성립하는 한 가지 특수한 경우는 비용 함수가 사각 부등식(quadrangle inequality)을 만족할 때, 즉 모든 $a \leq b \leq c \leq d$에 대해 $C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$가 성립할 때입니다. 많은 분할 정복 DP 문제는 볼록 껍질 트릭으로도 풀 수 있으며, 그 반대도 마찬가지입니다. 두 가지를 모두 알고 이해해 두면 유용합니다!

연습 문제

참고 문헌