[알고리즘]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

 

 

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