티스토리 뷰

공부

Knuth Optimization - Dynamic Programming

전명우 2016. 6. 23. 15:03

Knuth Optimization은 Dynamic Programming에서 점화식이 특정 조건을 만족할 때 활용할 수 있는 최적화 기법이다.


조건 1) DP 점화식 꼴

$D[i][j] = \min_{i < k < j}(D[i][k] + D[k][j]) + C[i][j]$

조건 2) Quadrangle Inequalty (사각부등식)

$C[a][c] + C[b][d] \leq C[a][d] + C[b][c], a \leq b \leq c \leq d$

조건 3) Monotonicity (단조성)

$C[b][c] \leq C[a][d], a \leq b \leq c \leq d$


조건 2와 조건 3을 만족하면 $A[i][j]$ = $D[i][j]$가 최소가 되기 위한 가장 작은 $k$라고 했을 때 아래 식을 만족한다.

$A[i][j-1] \leq A[i][j] \leq A[i+1][j]$

이와 관련된 증명은 여기에 기술되어 있다.

위 부등식을 통해 원래 $O(N^3)$으로 해결되는 것이 $O(N^2)$에 해결된다.


예시 문제로 2015년 인터넷 예선 F번 문제를 생각해보자.

F번 문제에서 DP 점화식은 다음과 같다.

$D[i][j] = \min_{i \leq 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] = \min_{i < k < j}(E[i][k]+E[k][j]) + C[i+1][j]$

여기서 $C[i][j]$는 i번째 수와 $j$번째 수 사이에 있는 수의 합이므로 위의 조건 2와 조건 3을 만족한다.


위 세 가지 조건을 모두 만족하므로 이 문제는 Knuth Optimization을 통해 최적화를 할 수 있다.

아래는 인터넷 예선 F번 문제를 $O(N^2)$ 시간에 해결하는 코드다.



'공부' 카테고리의 다른 글

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
링크
«   2024/03   »
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
글 보관함