티스토리 뷰

공부

Convex Hull Optimization

전명우 2016.08.23 19:05

Convex Hull Optimization이란, Convex Hull Trick이라고도 알려져있으며 특정 점화식 꼴을 가지는 동적계획법에서 시간을 줄이는 방법이다. IOI2002에 처음 나왔다고는 하나, 제대로 알려지기 시작한 것은 APIO2010 특공대 문제 이후라고 생각한다. 때문에 APIO2010 특공대 문제를 예시로 Convex Hull Optimization 설명을 시작하겠다.


$S_i = \sum_{k=1}^{i}{x_k}$ 를 정의하자. 단, $S_0 = 0$


DP 배열을 아래와 같이 정의한다.

$D_i$ = 1번부터 $i$번 병사까지 특공대를 나눌 때 전투력 합의 최대값. 단, $D_0 = 0$


이 때, 점화식은 아래와 같이 된다.

$D_i = \max(D[j] + A(S_i-S_j)^2 + B(S_i-S_j) + C)$


최종 답은 $D_N$이 되며 계산 시간복잡도는 $O(N^2)$이다.


이를 시간복잡도 $O(N)$에 해결하기 위해 점화식을 전개해보자.

$D_i = \max((-2AS_j)S_i + (AS_j^2 - BS_j + D_j)) + AS_i^2 + BS_i + C$


$AS_i^2 + BS_i + C$는 $j$와 무관한 $i$에 대한 상수이므로 $\max$ 함수 밖으로 뺄 수 있다. 그리고 $\max$ 함수 안에서는 $S_i$에 대한 다항식으로 표현했다.


$f_j(x) = (-2AS_j)x + (AS_j^2 - BS_j + D_j)$라고 정의하면 $A < 0$, $S_j > 0$이기 때문에 기울기가 양수인 일차함수가 된다. 때문에 $\max(f_j(S_i))$를 그래프로 그려보면 아래 그림처럼 볼록 껍데기의 부분 모양이 나온다.



$i$가 하나 증가할때마다 $\max$ 함수안에 일차 함수가 하나씩 더 추가되는 꼴이다. 이 문제에서 일차함수 $f_j(x)$의 기울기는 $j$가 커짐에 따라 커진다. 즉, 나중에 추가되는 일차 함수의 기울기가 크다. 따라서 볼록 껍데기를 스택을 통해 관리해줄 수 있다.


이제 $D_i$를 그래프와 직선 $x = S_i$의 교점의 $y$ 좌표를 구하는 것으로 계산할 수 있다. 이는 이분탐색을 통해 해결할 수도 있지만, $i$가 증가함에 따라 $x = S_i$도 증가하므로 이 또한 전체 $O(N)$ 시간안에 해결할 수 있다.


코드 보기


이 문제에서는 추가하는 일차함수의 기울기가 점점 커지고 교점을 찾는 $x$ 좌표가 점점 커지기 때문에 코딩하기 매우 편하다. 만약 교점을 찾는 $x$ 좌표가 경향이 없다면, 이분탐색을 통해 해결하면 된다. 만약 추가하는 일차함수의 기울기에 경향이 없다면 그래프는 스택이 아닌 set을 통해 관리되어야하며, 코딩이 까다로운 편이다. 볼록 껍데기를 이루는 그래프의 기울기는 항상 커져야함을 이용해 set에서 lower_bound 함수 등을 활용하여 코딩한다. 이 경우 연습 문제로 ACM ICPC World Finals 2011 F번 문제(해법)가 있다.

저작자 표시
신고

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

트리의 지름 구하기  (0) 2016.10.11
Convex Hull Optimization  (4) 2016.08.23
가장 먼 두 점 구하기  (4) 2016.07.17
Building Heap in Linear Time  (2) 2016.07.01
String Matching Algorithm  (4) 2016.06.24
Persistent Segment Tree  (4) 2016.06.23
댓글
댓글쓰기 폼