Knuth's Optimization

Knuth's Optimization은 Dynamic Programming의 점화식이 아래와 같은 특정 조건을 만족하는 경우 사용할 수 있는 "최적화" 기법이다.

 

i) DP 점화식 형태

 

$ dp[i][j] = min(dp[i][k] + dp[k+1][j]) + C[i][j] $      $ (i\le k<j)$ , C는 Cost

 

ii) 사각 부등식 (Quadrangle Inequality)

 

$ C[a][c] + C[b][d] \le C[a][d] + C[b][c] $

 

iii) 단조성 (Monotonicity) 

 

$ C[b][c] \le C[a][d] $    $ (a\le b\le c\le d)$

 

위 세 조건을 만족하는 경우 아래와 같은 성질을 만족한다. 

 

$ A[i][j] $ = "$ D[i][j] $ 가 최소가 되기 위한 가장 작은 k" 이면   

$$ A[i][j-1] \le A[i][j] \le A[i+1][j] $$

 

증명과정은 귀류법을 이용하여 조건 2가 성립하지 않는 모순을 보인다. (자세한 과정은 생략...)

 

 

Knuth's Optimization을 이용하면 $ O(n^3) $ 의 시간복잡도를 $ O(n^2) $ 로 줄일 수 있다. 

기존의 Dynamic Programming 기법을 이용하여, i)의 DP 점화식 형태를 풀게 되면 아래와 같이 코드를 작성할 수 있다. 

 

 

for(i=1; i<=n; i++){ //초기화
    dp[i][i] = 0;
}
 
for(i=1; i<=n; i++){
    for(j=i; j<n; j++){
            for(k=j+1; k<i; k++){
                dp[i][j] = min(dp[i][j] , dp[i][k]+dp[k+1][j]);
              }
               dp[i][j] += C[i][j];
    }
}

for(i=1; i<=n; i++){ //초기화
    dp[i][i] = 0;
    C[i][i] = i;
}
 
for(i=1; i<=n; i++){
    for(j=i; j<n; j++){
           dp[i][j] = MAX;
        for(k=A[i][j-1]; k<=A[i+1][j]; k++){ //상수번 반복
            if(dp[i][j] > dp[i][k] + dp[k+1][j]){
                dp[i][j] = dp[i][k] + dp[k+1][j];
                A[i][j] = k;
            }
        }
        dp[i][j] += C[i][j];
    }
}

Knuth's Optimization을 이용하는 대표적인 예시 문제는 BOJ 11066번 <파일 합치기>가 있다. 

(https://www.acmicpc.net/problem/11066)

 

풀이 : https://wogud6792.tistory.com/21