Dynamic Programming을 공부하다보니 문제 해결을 최적화하는 여러 가지 방법이 있다는 것을 알게 되었습니다.
커누스 최적화는 이런 DP 문제를 최적화하는 방법 중에 하나입니다.
특정 조건이 충족되면 사용할 수 있으며, \(O(n^{3})\)의 시간 복잡도를 \(O(n^{2})\)으로 최적화할 수 있습니다.
저는 아직 이 방법에 대해서 충분히 이해하진 못하였으나, 의외로 간단하기 때문에 잘 기억해두었다가 필요할 때에 다시 사용해보면 좋을 것 같습니다.
혹시 오류가 있다면 댓글로 남겨주시면 참고하여 수정하도록 하겠습니다.
커누스 최적화를 사용하기 위한 조건은 세 가지이며 다음과 같습니다.
첫째, 점화식의 형태가 다음과 같아야 합니다.
\(dp(i,j)=\displaystyle\min_{i\leq k<j}\left[dp(i,k)+dp(k+1,j)+C(i,j)\right]\)
둘째와 셋째는 \(a\leq b\leq c\leq d\)일 때, 다음을 만족해야합니다.
\(C(b,c)\leq C(a,d)\)
이것을 monotonicity, 단조성이라고 표현하는 것 같습니다.
\(C(a,c)+C(b,d)\leq C(a,d)+C(b,c)\)
이것은 Quadrangle Inequality[QI], 사각부등식, Monge array 등으로 표현하는 것 같습니다.
위의 조건들을 만족할 때, 첫째 조건의 점화식에서 \(dp(i,j)\)가 최소가 되는 \(k\)를 \(opt(i,j)\)라고 하면 다음과 같은 수식이 성립하게 됩니다.
\[opt(i,j-1)\leq opt(i,j)\leq opt(i+1,j)\]
위 수식을 이용하여 알고리즘의 복잡도를 최적화하면 \(k\)를 찾는데 필요했던 \(O(n^{2})\)을 \(O(n)\)으로 줄일 수 있어서 총 \(O(n^{2})\)으로 문제를 해결할 수 있게 됩니다.
위와 같은 수식이 왜 성립하는지 증명하는 것을 이해하기는 지금의 단계에선 무척 어렵지만 앞으로 조건만 맞다면 한 번 사용해보고자 합니다.
또한 \(C(i,j)\)가 또 다른 형태로 특수한 경우에는 \(O(n\log n)\)으로 최적화할 수 있는 방법이 있다고 합니다.
아직 이런 방법의 작은 부분조차 이해하기 어렵지만, 하나씩 공부해가며 내 것으로 만드는 재미가 있는 것 같습니다.
이상으로 포스팅을 마치겠습니다.
참고
https://koosaga.com/243
https://cp-algorithms.com/dynamic_programming/knuth-optimization.html
