Knuth's Optimization
|
AI Summary
- Knuth’s Optimization은 최적 이진트리 문제에 적용되는 기법으로 시간복잡도를 (O(N^3))에서 (O(N^2))로 줄인다.
- 이 기법은 (dp[i][j] = \min_{i < k < j} {dp[i][k] + dp[k][j]} + C[i][j]) 형태의 점화식에 적용 가능하다.
- 최적의 분할점 (A[i][j])가 (A[i][j-1] \le A[i][j] \le A[i+1][j]) 조건을 만족해야 한다.
- 비용 함수 (C[i][j])는 사각 부등식과 단조성 조건을 반드시 만족해야 Knuth’s Optimization을 사용할 수 있다.
- 대표적인 예제로 백준 11066 문제를 들 수 있으며, 관련 참고자료들이 여러 웹사이트에 정리되어 있다.
Knuth’s Optimization
1. Introduction
- Knuth’s Optimization은 최적 이진트리 문제(optimal binary tree problems)에 적용하는 특별한 Optimization 이다.
- 시간복잡도(time complexity)을(를) \(O(N^3)\)에서 \(O(N^2)\)로 줄인다.
- 다음의 Conditions 들을 만족해야 활용가능하다.
2. Conditions
- 반복되는 구조가 다음의 케이스 일 때 활용 가능
- \[dp[i][j] = \min_{i < k < j}{dp[i][k] + dp[k][j]} + C[i][j]\]
- 적용가능성의 충분 조건은
- \[A[i][j - 1] \le A[i][j] \le A[i + 1][j]\]
- Where,
- \(A[i][j]\)은(는) 최적의 답을 주는 가장 작은 k
- \[dp[i][j] = dp[i - 1][k] + C[k][j]\]
- \(C[i][j]\)는 주어진 cost function
- 가장 중요한 것은 Knuth’s Optimization은 \(C[i][j]\)이 다음의 두 조건을 만족해야 활용 가능
- Quadrangle inequality (사각 부등식)
- \[C[a][c] + C[b][d] \le C[a][d] + C[b][c], a \le b \le c \le d\]
- Monotonicity (단조성)
- \[C[b][c] \le C[a][d], a \le b \le c \le d\]
3. Example Code
4. References