DP Optimization: CHT, D&C, Knuth, SMAWK

정의

일반 DP 를 O(N²) 또는 O(N³) 에서 O(N log N) 또는 O(N) 으로 낮추는 여러 최적화 기법의 총칭입니다. 모두 특정 조건 (monotone, concave, quadrangle inequality) 이 성립할 때만 적용 가능합니다.

문제 상황

전형적인 DP 전환 문제를 만났을 때, 아래 형태인지 먼저 확인합니다.

// 형태 A: CHT / SMAWK
dp[i] = min over j<i of { f(j) * x[i] + g(j) }
// f(j) = 기울기, x[i] = 현재 값, g(j) = 절편

// 형태 B: D&C Optimization
dp[i][j] = min over k < j of { dp[i-1][k] + cost(k, j) }
// 최적 k 가 j 에 대해 단조 증가

// 형태 C: Knuth
dp[i][j] = min over i <= k <= j of { dp[i][k] + dp[k][j] + w(i, j) }
// w 가 QI + 단조 만족

시각화

4 가지 기법의 적용 시나리오와 복잡도.

flowchart TD
    Start["DP 전환 문제"]
    Q1{"dp[i] = min f(j)*x[i]+g(j)?"}
    Q2{"최적 k 단조 증가?"}
    Q3{"구간 DP, w가 QI?"}
    Q4{"Monge 행렬?"}

    CHT["CHT\nO(N log N) / O(N)"]
    DnC["D&C Optimization\nO(N log N)"]
    Knuth["Knuth Optimization\nO(N^2)"]
    SMAWK["SMAWK\nO(N)"]
    Naive["Naive O(N^2) / O(N^3)"]

    Start --> Q1
    Q1 -->|"Yes"| CHT
    Q1 -->|"No"| Q2
    Q2 -->|"Yes"| DnC
    Q2 -->|"No"| Q3
    Q3 -->|"Yes"| Knuth
    Q3 -->|"No"| Q4
    Q4 -->|"Yes"| SMAWK
    Q4 -->|"No"| Naive

핵심 아이디어

1. Convex Hull Trick (CHT)

dp[i] = min_{j<i}(a[j] * x[i] + b[j]) 형태. 선형 함수 집합의 최솟값 = 하부 볼록 껍질 (lower envelope).

• Li-Chao Tree: 임의 삽입 순서, O(log N) per query/update
• 단조 CHT (Monotone Stack): 기울기 a[j] 단조 증가이면 O(1) push, O(1)/O(log N) query
• Kinetic Heaps: 온라인, 자동 최솟값 추적

전용 Li-Chao Tree 참조.

2. Divide and Conquer Optimization

dp[i][j] = min_{k}(dp[i-1][k] + cost(k, j)) 에서 최적 k 가 j 에 대해 단조 증가 하면 O(N²) → O(N log N).

핵심: 구간 [lo, hi] 의 중간 mid 를 계산하고, 가능한 k 범위를 재귀적으로 좁힘.

3. Knuth Optimization

dp[i][j] = min_{i<=k<=j}(dp[i][k] + dp[k][j]) + w(i,j) 에서 Quadrangle Inequality (QI) 와 단조성 이 성립하면 O(N³) → O(N²).

QI: w(a,c) + w(b,d) <= w(a,d) + w(b,c) (a<=b<=c<=d).

4. SMAWK / Monge

Monge 행렬: 모든 2×2 부분행렬이 QI 를 만족하는 행렬. SMAWK 알고리즘으로 각 행의 최솟값을 O(N) 에 계산.

알고리즘

CHT (단조 스택, 오프라인)

라인 관리 스택 stk:
  add(a, b):  // y = a*x + b 삽입
      새 직선 L
      while stk.size() >= 2:
          if stk[-2] 와 stk[-1] 의 교점 >= stk[-1] 와 L 의 교점:
              stk.pop()
          else: break
      stk.push(L)

  query(x):   // 최솟값 직선의 y값
      while stk.size() >= 2:
          if stk[0].eval(x) >= stk[1].eval(x):
              stk.pop_front()
          else: break
      return stk[0].eval(x)

D&C Optimization

solve(lo, hi, optL, optR):
    if lo > hi: return
    mid = (lo + hi) / 2
    best_k = optL
    dp[i][mid] = INF
    for k in [optL .. min(mid, optR)]:
        cand = dp[i-1][k] + cost(k, mid)
        if cand < dp[i][mid]:
            dp[i][mid] = cand
            best_k = k
    solve(lo, mid-1, optL, best_k)
    solve(mid+1, hi, best_k, optR)

Knuth Optimization

// opt[i][j] = dp[i][j] 의 최적 k
for gap in 1..n:
    for i in 0..n-gap:
        j = i + gap
        dp[i][j] = INF
        for k in opt[i][j-1]..opt[i+1][j]:
            if dp[i][k] + dp[k][j] + w(i,j) < dp[i][j]:
                dp[i][j] = dp[i][k] + dp[k][j] + w(i,j)
                opt[i][j] = k

구현

D&C Optimization

#include <bits/stdc++.h>
using namespace std;
​
const long long INF = 1e18;
int n, m;
vector<long long> prev_dp, cur_dp;
​
// cost(k, j): 구체적인 문제마다 다름
long long cost(int k, int j) {
  // 예: prefix sum 기반 비용
  return (long long)(j - k) * (j - k);
}
​
void solve(int lo, int hi, int optL, int optR) {
  if (lo > hi) return;
  int mid = (lo + hi) / 2;
  int best_k = optL;
  cur_dp[mid] = INF;
  for (int k = optL; k <= min(mid - 1, optR); k++) {
      if (prev_dp[k] == INF) continue;
      long long cand = prev_dp[k] + cost(k, mid);
      if (cand < cur_dp[mid]) {
          cur_dp[mid] = cand;
          best_k = k;
      }
  }
  solve(lo, mid - 1, optL, best_k);
  solve(mid + 1, hi, best_k, optR);
}
​
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  prev_dp.resize(n + 1, INF);
  cur_dp.resize(n + 1, INF);
  prev_dp[0] = 0;
  // i번째 분할
  for (int i = 1; i <= m; i++) {
      fill(cur_dp.begin(), cur_dp.end(), INF);
      solve(1, n, 0, n - 1);
      swap(prev_dp, cur_dp);
  }
  cout << prev_dp[n] << "\n";
  return 0;
}

// n=5, m=2 (2그룹으로 분할)
// 예시 cost = (j-k)^2
// dp[5] = 최소 분할 비용
8

Knuth Optimization

// Knuth: 구간 DP O(N^2)
// 전제: w(i,j) 가 QI + 단조 만족
vector<vector<long long>> dp(n+1, vector<long long>(n+1, INF));
vector<vector<int>> opt(n+1, vector<int>(n+1, 0));

for (int i = 0; i <= n; i++) { dp[i][i] = 0; opt[i][i] = i; }

for (int gap = 1; gap <= n; gap++) {
    for (int i = 0; i + gap <= n; i++) {
        int j = i + gap;
        dp[i][j] = INF;
        for (int k = opt[i][j-1]; k <= opt[i+1][j]; k++) {
            long long cand = dp[i][k] + dp[k][j] + w(i, j);
            if (cand < dp[i][j]) {
                dp[i][j] = cand;
                opt[i][j] = k;
            }
        }
    }
}

복잡도

함정

• 적용 가능한 기법이 여러 가지라면 CHT > D&C > Knuth 순으로 빠름.
• SMAWK 는 구현이 까다로워 실전에서는 LARSSON 또는 Divide Conquer 로 대체하는 경우가 많음.

BOJ

관련 위키

• Li-Chao Tree (CHT 자료구조)
• DP 기초
• DP Bitfield (비트마스크 DP)
• Knapsack DP (배낭 DP)
• Knuth Optimization (전용 문서)
• D&C Optimization (전용 문서)
• Convex Hull Trick (전용 문서)