티스토리 뷰
Knuth Optimization은 Dynamic Programming에서 점화식이 특정 조건을 만족할 때 활용할 수 있는 최적화 기법이다.
조건 1) DP 점화식 꼴
D[i][j]=mini<k<j(D[i][k]+D[k][j])+C[i][j]
조건 2) Quadrangle Inequalty (사각부등식)
C[a][c]+C[b][d]≤C[a][d]+C[b][c],a≤b≤c≤d
조건 3) Monotonicity (단조성)
C[b][c]≤C[a][d],a≤b≤c≤d
조건 2와 조건 3을 만족하면 A[i][j] = D[i][j]가 최소가 되기 위한 가장 작은 k라고 했을 때 아래 식을 만족한다.
A[i][j−1]≤A[i][j]≤A[i+1][j]
이와 관련된 증명은 여기에 기술되어 있다.
위 부등식을 통해 원래 O(N3)으로 해결되는 것이 O(N2)에 해결된다.
예시 문제로 2015년 인터넷 예선 F번 문제를 생각해보자.
F번 문제에서 DP 점화식은 다음과 같다.
D[i][j]=mini≤k<j(D[i][k]+D[k+1][j])+C[i][j]
조건 1의 점화식 꼴을 맞춰주기 위해 새로운 DP 배열 E[i][j]=D[i+1][j]을 정의하자.
E의 점화식은 아래와 같다.
E[i][j]=mini<k<j(E[i][k]+E[k][j])+C[i+1][j]
여기서 C[i][j]는 i번째 수와 j번째 수 사이에 있는 수의 합이므로 위의 조건 2와 조건 3을 만족한다.
위 세 가지 조건을 모두 만족하므로 이 문제는 Knuth Optimization을 통해 최적화를 할 수 있다.
아래는 인터넷 예선 F번 문제를 O(N2) 시간에 해결하는 코드다.
'공부' 카테고리의 다른 글
Persistent Segment Tree (6) | 2016.06.23 |
---|---|
Divide & Conquer Optimization (3) | 2016.06.23 |
Majority Vote Algorithm (2) | 2016.06.23 |
Grundy Number (0) | 2014.11.13 |
Suffix Array와 LCP (14) | 2014.08.14 |
- Total
- Today
- Yesterday
- BOI 2001
- Knuth Optimization
- Dijkstra
- optimization
- Parametric Search
- dynamic programming
- vote
- Dynamic Pramming
- Divide & Conquer
- Algorithm
- z-trening
- majority
- ioi
- USACO
- Splay Tree
- TRIE
- Segment tree
- IOI2011
- BOI 2009
- Greedy Method
- Boyer
- Boyer-Moore Majority Vote Algorithm
- BOI
- HackerRank
- IOI2013
- Tree
- moore
- IOI2014
- idea
- IOI2012
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |