티스토리 뷰

공부

Divide & Conquer Optimization

전명우 2016.06.23 16:31

Divide & Conquer Optimization은 특정 조건을 만족할 때 활용할 수 있는 최적화 기법이다. 주로 Dynamic Programming에서 쓰인다고 생각할 수 있으나, Dynamic Programming이 아닌 상황에서도 널리 쓰일 수 있다.


조건 1) DP 점화식 꼴

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

조건 2) $A[t][i]$는 $D[t][i]$를 만족시키는 최소 $k$라 할 때 아래 부등식을 만족

$A[t][i] \leq A[t][i+1]$


위 두 조건을 만족하면 원래 $O(KN^2)$의 시간복잡도를 갖는 DP를 Divide & Conquer를 통해 $O(KN \lg N)$에 해결 할 수 있다. 여기서 $K$는 단계 수(가능한 $t$의 종류)를 의미한다.


Divide & Conquer(분할정복)을 이용해 이를 한 단계 마다 $O(N \lg N)$ 시간안에 해결하는 방법은 다음과 같다.

여기서 단계별로 시간복잡도가 $O(N \lg N)$이라는 것을 보이기 위해, 11번째 줄에 있는 for문이 돌아가는 횟수를 생각해보자. for문이 돌아가는 횟수가 $N \lg N$에 비례하다는 것을 어렵지 않게 보일 수 있다.


단계 수 $K=1$인 경우도 종종 있는데, 이 때 점화식을 조건 1 꼴로 쓸 수는 있지만 Dynamic Programming이 아니라고 볼 수 있다. $K=1$인 경우 이를 이용하여 해결하는 문제는 대표적으로 IOI 2014 Holiday, BOJ 11001번 김치, ICPC WF2016 B번 문제가 있다.


이를 이용해 해결할 수 있는 다른 문제로는 ICPC WF 2016 B번 문제가 있다.

조건 2를 만족하는 특수한 경우들

1) Quadrangle Inequalty (사각부등식) 만족하는 경우

조건 1의 점화식 꼴이고, 비용 $C$가 사각부등식 $C[a][c] + C[b][d] \leq C[a][d] + C[b][c]$를 만족하는 경우 조건 2도 만족한다.

증명 보기


저작자 표시
신고

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

String Matching Algorithm  (4) 2016.06.24
Persistent Segment Tree  (4) 2016.06.23
Divide & Conquer Optimization  (0) 2016.06.23
Knuth Optimization - Dynamic Programming  (2) 2016.06.23
Majority Vote Algorithm  (1) 2016.06.23
Grundy Number  (0) 2014.11.13
댓글
댓글쓰기 폼