크누스 최적화 (Knuth Optimization)

정의

크누스 최적화 (Knuth Optimization) 는 구간 DP dp[i][j] = min(dp[i][k-1] + dp[k][j]) + C[i][j] 에서 최적 분할점 k = opt[i][j] 의 단조성 을 이용해 시간 복잡도를 O(N^3) 에서 O(N^2) 으로 줄이는 기법.

1971년 Donald E. Knuth 가 Optimal Binary Search Tree (OBST) 의 O(N^2) 해법을 발표하며 처음 사용.

문제 상황과 동기

왜 필요한가

구간 DP: dp[i][j] = min_k (dp[i][k-1] + dp[k][j]) + C[i][j] (i ≤ k ≤ j).

• naive: 모든 k 를 검사, O(N) per state. 상태 N^2 개. 총 O(N^3).
• N=2000 이면 8*10^9. 절대 통과 불가.

Knuth 최적화의 돌파구: C[i][j] 가 사각 부등식 (quadrangle inequality) 과 단조성 (monotonicity) 을 만족하면, opt[i][j] 가 opt[i][j-1] <= opt[i][j] <= opt[i+1][j] 를 만족한다. 각 dp[i][j] 의 k 탐색 범위가 O(N) 에서 O(1) amortized 로 감소. 전체 O(N^2).

전제 조건

C[i][j] 가 다음 두 조건을 만족해야 한다.

1. 사각 부등식: i ≤ i’ ≤ j ≤ j’ 일 때 C[i][j] + C[i’][j’] ≤ C[i][j’] + C[i’][j]
2. 단조성: i ≤ i’ ≤ j ≤ j’ 일 때 C[i’][j] ≤ C[i][j’] (또는 C[i][j] 가 i 와 j 에 대해 단조 증가)

이 두 조건이 DP 의 최적 분할점 단조성을 보장한다.

시각화

핵심 아이디어

opt[i][j-1] <= opt[i][j] <= opt[i+1][j]

증명 스케치:
  사각 부등식 -> dp 가 사각 부등식을 만족 (induction)
  사각 부등식 -> 단조성 (monotone decision point)
  귀류법: opt[i][j] < opt[i][j-1] 이라면 모순 유도

이 부등식을 이용하면 dp[i][j] 의 k 탐색 범위를 [opt[i][j-1], opt[i+1][j]] 로 제한할 수 있다. 구간 길이 순으로 바깥 루프 (len = 2..N) 를 돌면, 각 i, j 에 대해 검사하는 k 의 총합이 O(N^2) 임이 보장된다.

알고리즘

KnuthDP(a[1..N]):
    for i = 1..N:
        dp[i][i] = 0         # base
        opt[i][i] = i
        ps[i] = ps[i-1] + a[i]  # prefix sum for C

    for len = 2..N:           # 구간 길이
        for i = 1..N-len+1:   # 시작점
            j = i + len - 1   # 끝점
            dp[i][j] = INF
            sum = C(i, j)     # 예: 구간 합
            # k 범위: opt[i][j-1] ~ opt[i+1][j]
            for k = opt[i][j-1] .. opt[i+1][j]:
                val = dp[i][k-1] + dp[k][j] + sum
                if val < dp[i][j]:
                    dp[i][j] = val
                    opt[i][j] = k
    return dp[1][N]

구현

아래는 파일 합치기 (BOJ 11066) 문제. N 개의 파일을 하나로 합치는 최소 비용. Knuth 최적화로 O(N^3) -> O(N^2).

// Knuth Optimization: O(N^2)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n; cin >> n;
  vector<int> a(n + 1), ps(n + 1);
  vector<vector<int>> dp(n + 1, vector<int>(n + 1));
  vector<vector<int>> opt(n + 1, vector<int>(n + 1));
  for (int i = 1; i <= n; i++) {
      cin >> a[i];
      ps[i] = ps[i - 1] + a[i];
      dp[i][i] = 0;
      opt[i][i] = i;
  }
  for (int len = 2; len <= n; len++) {
      for (int i = 1; i + len - 1 <= n; i++) {
          int j = i + len - 1;
          dp[i][j] = INF;
          int sum = ps[j] - ps[i - 1];
          int start = opt[i][j - 1];
          int end = min(j - 1, opt[i + 1][j]);
          for (int k = start; k <= end; k++) {
              int val = dp[i][k] + dp[k + 1][j] + sum;
              if (val < dp[i][j]) {
                  dp[i][j] = val;
                  opt[i][j] = k;
              }
          }
      }
  }
  cout << dp[1][n] << '
';
}

import sys
input = sys.stdin.readline
INF = 10 ** 9
​
n = int(input())
a = [0] + list(map(int, input().split()))
ps = [0] * (n + 1)
for i in range(1, n + 1):
  ps[i] = ps[i - 1] + a[i]
​
dp = [[0] * (n + 1) for _ in range(n + 1)]
opt = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
  dp[i][i] = 0
  opt[i][i] = i
​
for length in range(2, n + 1):
  for i in range(1, n - length + 2):
      j = i + length - 1
      dp[i][j] = INF
      s = ps[j] - ps[i - 1]
      start = opt[i][j - 1]
      end = min(j - 1, opt[i + 1][j])
      for k in range(start, end + 1):
          val = dp[i][k] + dp[k + 1][j] + s
          if val < dp[i][j]:
              dp[i][j] = val
              opt[i][j] = k
​
print(dp[1][n])

4
40 30 30 50

300

5
10 20 30 40 50

330

복잡도

각 행 i 에 대해 k 검사 범위의 합이 O(N) 이고, 이걸 N 개의 i 에 대해 O(N^2). naive 대비 N 배 향상.

변형 / 활용

함정

1. 사각 부등식 검증 생략

Knuth 가 적용되는지 수학적으로 증명하지 않고 쓰면 틀린다. C[i][j] 가 단순 구간 합이면 항상 성립하지만, 복잡한 비용 함수는 검증 필수.

2. opt 범위의 경계 처리

opt[i+1][j] 가 i+1 > j 인 경우 (i = j) 접근 오류. 항상 opt[i][i] = i 로 초기화하고 opt[i+1][j] 는 opt[i+1][j] 가 정의된 경우만 사용.

3. opt 테이블 초기값

opt[i][i] = i (base). opt[i][j-1] 과 opt[i+1][j] 가 각각 len-1 에서 계산되도록 구간 길이 순으로 순회.

4. dp 테이블 크기와 overflow

파일 합치기처럼 누적 합이 커지면 int overflow. long long 사용.

BOJ 연습 문제

참고

• 분할정복 DP 최적화
• Convex Hull Trick
• Aliens Trick
• 덱 트릭