티스토리 뷰

공부

Knuth Optimization - Dynamic Programming

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

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],abcd

조건 3) Monotonicity (단조성)

C[b][c]C[a][d],abcd


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

A[i][j1]A[i][j]A[i+1][j]

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

위 부등식을 통해 원래 O(N3)으로 해결되는 것이 O(N2)에 해결된다.


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

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

D[i][j]=minik<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
링크
«   2025/05   »
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
글 보관함