[알고리즘]Knuth's optimization 크누스 최적화

백준의 11066번 문제를 풀다가 발견한 최적화 기법이다. (문제를 해결했던 코드)

 

이 알고리즘은 동적 계획법으로 해결하는 문제에서 특수한 조건일 때 시간 복잡도를 $O(n^3)$에서 $O(n^2)$까지 줄일 수 있는 강력한 알고리즘이다.

사용할 수 있는 동적 계획법의 종류에는 이차원 배열인 $C$와 $C$를 이용한 Dynamic Programming을 적용한 이차원배열인 $DP$가 있다고 했을 때 다음과 같은 조건이 필요하다.

1. 점화식의 형태: $DP[i][j] = min(DP[i][k] + DP[k][j]) + C[i][j]$    $(i < k < j)$
2. 사각 부등식: $C[a][c] + C[b][d] <= C[a][d] + C[b][c]$    $(a <= b <= c <= d)$
3. 단조성: $C[b][c] <= C[a][d]$    $(a <= b <= c <= d)$

문제를 풀 때는 누적합을 이중 리스트를 사용하지 않고 단순히 하나의 리스트에서 인덱싱해서 사용했는데, 이것을 이중 리스트로 구성했다고 했을 때 ($C[i][j]$란 $f[i]$에서 $f[j]$까지의 연속합) 조건 3은 당연히 만족하게 된다.

 

조건 2의 경우에는 다르게 표현하면 $(a \sim d까지\ 연속합 + b \sim c까지 연속합) <= (a \sim d까지 연속합 + b \sim c까지 연속합)$으로 같음이 만족하기 때문에 만족하는 것을 알 수 있다.

 

조건 2와 조건 3을 만족하면 조건 1의 형태의 점화식을 이용해서 문제를 해결할 수 있다.

• $DP[i][j] = min(DP[i][k] + DP[k + 1][j]) + C[i][j]$ $(i <= k < j)$

위의 형태로 점화식을 사용했는데, 이때 $E[i][j] = DP[i + 1][j]$인 $E$를 사용한다면

• $E[i][j] = min(E[i][k] + E[k][j]) + C[i][j]$ $(i < k < j)$

위의 형태로 바꿀 수 있기 때문에 성립한다. 이때 $E[i][k]$는 $i$부터 $k-1$까지의 누적합이라고 볼 수 있다.

 

추가적으로 조건 1의 점화식을 만들었을 때 $minimum$을 결정하는 $k$를 $A[i][j]$에 저장한다고 할 때

• $A[i][j - 1] <= A[i][j] = k < A[i + 1][j]$

위의 식을 만족하게 된다.

 

문제를 풀 때 위의 $k$를 결정할 수 있는 식은 쓰지 않았지만, 위의 부등식 덕분에 시간 복잡도가 줄 수 있는 것이다!

 

$DP[i][j]$를 채울 때 $i$와 $j$는 무조건 방문해서 채워나가기 때문에 $O(n^2)$ 걸리지만, $k$까지 $i$부터 $j$까지 돌 필요를 줄였기 때문이다.

 

위의 $k$를 결정할 수 있는 조건을 사용하지 않아도 통과했지만, $i$와 $j$사이의 간격이 매우 크게 된다면 다시 시간 초과가 발생할 것이다.

 

 

 

<참고>

https://blog.myungwoo.kr/98

https://sexycoder.tistory.com/92

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다