Knuth 최적화¶

Knuth-Yao 속도 향상(Knuth-Yao Speedup)이라고도 불리는 Knuth 최적화는 구간에 대한 동적 계획법의 특수한 경우로, 풀이의 시간 복잡도를 선형 인자만큼, 즉 표준 구간 DP의 $O(n^3)$에서 $O(n^2)$로 최적화할 수 있습니다.

조건¶

이 속도 향상 기법은 다음 형태의 전이에 적용됩니다.

$$dp(i, j) = \min_{i \leq k < j} [ dp(i, k) + dp(k+1, j) + C(i, j) ].$$

분할 정복 DP와 마찬가지로, $opt(i, j)$를 전이식의 값을 최소화하는 $k$ 중 최댓값이라고 합시다(이 글에서는 이후 $opt$를 "최적 분할점"이라고 부릅니다). 이 최적화를 적용하려면 다음이 성립해야 합니다.

$$opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j).$$

비용 함수 $C$가 $a \leq b \leq c \leq d$에 대해 다음 조건들을 만족하면 이것이 참임을 보일 수 있습니다.

$C(b, c) \leq C(a, d)$;
$C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$ (사각 부등식 [QI]).

이 결과는 아래에서 증명합니다.

알고리즘¶

$dp(i, j)$보다 $dp(i, j-1)$과 $dp(i+1, j)$를 먼저 계산하도록 dp 상태를 처리하고, 그 과정에서 $opt(i, j-1)$과 $opt(i+1, j)$도 함께 계산합시다. 그러면 $opt(i, j)$를 계산할 때 $k$의 값을 $i$부터 $j-1$까지 모두 시험하는 대신, $opt(i, j-1)$부터 $opt(i+1, j)$까지만 시험하면 됩니다. $(i,j)$ 쌍을 이 순서로 처리하려면 $i$는 최댓값에서 최솟값으로, $j$는 $i+1$에서 최댓값으로 진행하는 중첩 for 루프를 사용하는 것으로 충분합니다.

일반적인 구현¶

구현 방식은 다양하지만, 꽤 일반적인 예시를 소개합니다. 코드의 구조는 구간 DP의 구조와 거의 동일합니다.

int solve() {
    int N;
    ... // read N and input
    int dp[N][N], opt[N][N];

    auto C = [&](int i, int j) {
        ... // Implement cost function C.
    };

    for (int i = 0; i < N; i++) {
        opt[i][i] = i;
        ... // Initialize dp[i][i] according to the problem
    }

    for (int i = N-2; i >= 0; i--) {
        for (int j = i+1; j < N; j++) {
            int mn = INT_MAX;
            int cost = C(i, j);
            for (int k = opt[i][j-1]; k <= min(j-1, opt[i+1][j]); k++) {
                if (mn >= dp[i][k] + dp[k+1][j] + cost) {
                    opt[i][j] = k; 
                    mn = dp[i][k] + dp[k+1][j] + cost; 
                }
            }
            dp[i][j] = mn; 
        }
    }

    return dp[0][N-1];
}

복잡도¶

이 알고리즘의 복잡도는 다음 합으로 추정할 수 있습니다.

$$ \sum\limits_{i=1}^N \sum\limits_{j=i+1}^N [opt(i+1,j)-opt(i,j-1)] = \sum\limits_{i=1}^N \sum\limits_{j=i}^{N-1} [opt(i+1,j+1)-opt(i,j)]. $$

보시다시피, 이 식의 항 대부분은 서로 상쇄되며, $j=N-1$인 양의 항과 $i=1$인 음의 항만 남습니다. 따라서 전체 합은 다음과 같이 추정할 수 있습니다.

$$ \sum\limits_{k=1}^N[opt(k,N)-opt(1,k)] = O(n^2), $$

이는 일반적인 구간 DP를 사용했을 때의 $O(n^3)$과 대비됩니다.

실전에서¶

Knuth 최적화가 가장 흔히 적용되는 곳은 주어진 전이를 갖는 구간 DP입니다. 유일한 어려움은 비용 함수가 주어진 조건들을 만족함을 증명하는 것입니다. 가장 간단한 경우는 비용 함수 $C(i, j)$가 (문제에 따라 정해지는) 어떤 배열의 부분 배열 $S[i, i+1, ..., j]$의 원소 합인 경우입니다. 그러나 때로는 비용 함수가 더 복잡할 수 있습니다.

dp 전이와 비용 함수에 대한 조건보다도, 이 최적화의 핵심은 최적 분할점에 대한 부등식이라는 점에 유의하십시오. 최적 이진 탐색 트리 문제(공교롭게도 이 최적화가 처음 고안된 원래 문제입니다)와 같은 일부 문제에서는 전이와 비용 함수가 덜 명확하지만, 그래도 $opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j)$임을 증명할 수 있으므로 이 최적화를 사용할 수 있습니다.

정당성 증명¶

$C(i,j)$의 조건을 바탕으로 이 알고리즘의 정당성을 증명하려면, 다음을 증명하는 것으로 충분합니다.

$$ opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j) $$

단, 주어진 조건들이 만족된다고 가정합니다.

보조정리

문제의 조건이 만족된다면 $dp(i, j)$ 역시 사각 부등식을 만족합니다.

증명

이 보조정리의 증명에는 강한 귀납법을 사용합니다. 이 증명은 Efficient Dynamic Programming Using Quadrangle Inequalities(사각 부등식을 이용한 효율적인 동적 계획법) 논문에서 가져온 것으로, 저자는 F. Frances Yao가 저술했으며, 이 논문에서 Knuth-Yao Speedup이 처음 소개되었습니다(이 명제는 논문의 보조정리 2.1입니다). 핵심 아이디어는 길이 $l = d - a$에 대해 귀납법을 적용하는 것입니다. $l = 1$인 경우는 자명합니다. $l > 1$인 경우에는 다음 2가지 경우를 고려합니다.

$b = c$
부등식은 $dp(a, b) + dp(b, d) \leq dp(a, d)$로 정리됩니다(이는 모든 $i$에 대해 $dp(i, i) = 0$이라고 가정한 것이며, 이 최적화를 사용하는 모든 문제가 이에 해당합니다). $opt(a,d) = z$라고 합시다.
- $z < b$이면,
  다음에 주목하십시오.
  
  $$ dp(a, b) \leq dp_{z}(a, b) = dp(a, z) + dp(z+1, b) + C(a, b). $$
  
  따라서,
  
  $$ dp(a, b) + dp(b, d) \leq dp(a, z) + dp(z+1, b) + dp(b, d) + C(a, b) $$
  
  귀납법 가정에 의해 $dp(z+1, b) + dp(b, d) \leq dp(z+1, d)$입니다. 또한 $C(a, b) \leq C(a, d)$임이 주어져 있습니다. 이 2가지 사실을 위의 부등식과 결합하면 원하는 결과를 얻습니다.
- $z \geq b$이면, 이 경우의 증명은 앞의 경우와 대칭적입니다.
$b < c$
$opt(b, c) = z$, $opt(a, d) = y$라고 합시다.
- $z \leq y$이면,
  
  $$ dp(a, c) + dp(b, d) \leq dp_{z}(a, c) + dp_{y}(b, d) $$
  
  여기서
  
  $$ dp_{z}(a, c) + dp_{y}(b, d) = C(a, c) + C(b, d) + dp(a, z) + dp(z+1, c) + dp(b, y) + dp(y+1, d). $$
  
  $C$에 대한 QI와, 인덱스 $z+1 \leq y+1 \leq c \leq d$에 대한 dp 상태의 QI(귀납법 가정에 의해 성립)를 함께 사용하면 원하는 결과를 얻습니다.
- $z > y$이면, 이 경우의 증명은 앞의 경우와 대칭적입니다.

이로써 보조정리의 증명이 완료됩니다.

이제 다음과 같은 설정을 생각해 봅시다. 2개의 인덱스 $i \leq p \leq q < j$가 있습니다. $dp_{k} = C(i, j) + dp(i, k) + dp(k+1, j)$로 둡니다.

다음을 보인다고 가정합시다.

$$ dp_{p}(i, j-1) \geq dp_{q}(i, j-1) \implies dp_{p}(i, j) \geq dp_{q}(i, j). $$

$q = opt(i, j-1)$로 두면, 정의에 의해 $dp_{p}(i, j-1) \geq dp_{q}(i, j-1)$입니다. 따라서 모든 $i \leq p \leq q$에 대해 이 부등식을 적용하면 $opt(i, j)$가 $opt(i, j-1)$ 이상임을 추론할 수 있으며, 이로써 부등식의 앞쪽 절반이 증명됩니다.

이제 어떤 인덱스 $p+1 \leq q+1 \leq j-1 \leq j$에 대해 QI를 사용하면 다음을 얻습니다.

$$\begin{align} &dp(p+1, j-1) + dp(q+1, j) ≤ dp(q+1, j-1) + dp(p+1, j) \\ \implies& (dp(i, p) + dp(p+1, j-1) + C(i, j-1)) + (dp(i, q) + dp(q+1, j) + C(i, j)) \\ \leq& (dp(i, q) + dp(q+1, j-1) + C(i, j-1)) + (dp(i, p) + dp(p+1, j) + C(i, j)) \\ \implies& dp_{p}(i, j-1) + dp_{q}(i, j) ≤ dp_{p}(i, j) + dp_{q}(i, j-1) \\ \implies& dp_{p}(i, j-1) - dp_{q}(i, j-1) ≤ dp_{p}(i, j) - dp_{q}(i, j) \\ \end{align}$$

마지막으로,

$$\begin{align} &dp_{p}(i, j-1) \geq dp_{q}(i, j-1) \\ &\implies 0 \leq dp_{p}(i, j-1) - dp_{q}(i, j-1) \leq dp_{p}(i, j) - dp_{q}(i, j) \\ &\implies dp_{p}(i, j) \geq dp_{q}(i, j) \end{align}$$

이로써 부등식의 첫 번째 부분, 즉 $opt(i, j-1) \leq opt(i, j)$가 증명됩니다. 두 번째 부분 $opt(i, j) \leq opt(i+1, j)$도 부등식 $dp(i, p) + dp(i+1, q) ≤ dp(i+1, p) + dp(i, q)$에서 출발하여 같은 아이디어로 보일 수 있습니다.

이로써 증명이 완료됩니다.