티스토리 뷰
이번엔 DP를 최적화하는 심화 기법에 대해서 알아보겠다. CHT, Convex Hull Optimization이라고도 불린다. 번역하면 볼록 껍질을 이용한 최적화 정도가 되겠다.
이름에서 볼록 껍질이 나오다시피 볼록 껍질을 응용해서 하나의 쿼리의 시간복잡도를 줄이는 것이다. 대표적으로 \(O(N)\)의 쿼리를 \(O(\log N)\)으로 줄이는 최솟값/최댓값 쿼리가 있다. 하지만 항상 사용할 수 있는 최적화 기법은 아니고, 최솟값/최댓값을 구하고자 하는 배열의 일부가 단조감소 혹은 단조증가할 때만 사용할 수 있다. 이렇게 말하면 너무 어려우니 예시를 보자.
아 그리고 이제 글에 \(\LaTeX\)이 적용이 돼서 기분이 너무 좋다. 이제 N^2나 a_1같은 표기 안봐도된다. 화살표도 \(\Rightarrow\) 이렇게 이쁘게 그릴수 있다. \(\mathfrak{A}\looparrowleft\aleph\dagger\) 히히 이랬는데 막 실제로 올라갈때는 안되고 그러는건 아니겠지..
13263번: 나무 자르기
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 < a2 < ... < an, b1 > b2 > ... > bn을 만족
www.acmicpc.net
대표적인 CHT를 사용하는 문제이다. N이 10만까지니 \(O(N^2)\)은 무리가 있고 \(O(N \log N)\)이나 \(O(N)\)까지 낮춰야 하겠다. 하지만 아주 특이한 조건이 있다. \(a\)는 구간 전체에서 증가, b는 구간 전체에서 감소한다는 조건이다. 우선 DP식을 세워보자. 일단 완전히 잘린 나무가 없으면 더 이상 나무를 자를 수 없고 \(a_1\)이 1이므로 첫번째 나무를 자르는 것은 강제된다. 그리고 \(b_{N}\)이 0이므로 N번째 나무를 자른다면 그 이후부터는 비용이 들지 않고 나무를 자를 수 있다. 이런 조건 때문에 이 문제는 좀 특이하게 DP식을 세운다.
DP[i] = i번째 나무를 높이 1로 만드는 데 드는 최소비용그리고 이런식으로 짠 DP는 아래 방법으로 계산할 수 있다.
DP[i] = min({DP[j] + a[j] * b[i], for (0 <= j < i)})???
조금 더 자세히 식을 써보겠다.
DP[i] = min({(DP[j] + b[j]) + (a[i] - 1)* b[j] , for (0 <= j < i)})이 말은 j번째 나무를 먼저 완전히 자르고(\(DP[j] + b[j]\)) 그 다음 i번째 나무를 높이 1로 만드는(\((a[i] - 1) \times b[j]\)) 것이다. 1번을 바로 자르고 오거나 중간에 다른 나무를 자르고 올 수도 있다. 그럼 문제에서 구하고자 하는 답은 N번째 나무를 자르는 최소 비용이므로 DP[N-1] + a[N-1]으로 표현할 수 있고, 결과적으로는 DP 배열을 채우는 것이 관건이다. 하지만 지금 쓴 식은 시간복잡도가 \(O(N^2)\)이므로 \(N\leq 100000\)으론 무리가 있다. 여기서 b가 감소한다는 조건을 사용한다.
위의 DP 식을 다시 보자. b의 값이 감소하므로 a[j]의 을 x축으로 생각해보자. 그러면 최솟값을 구해야 되는 내부의 j개의 항들을 기울기가 b[j]인 일차함수의 형태로 생각할 수 있고, 기울기가 감소하므로 모든 그래프를 한 평면에 그려보면 아래 사진처럼 나타날 것이다.
다시 쓰면, \(y = b[j] x + DP[j]\)의 일차함수 들에서 \(x\)로는 \(a[i]\)들이 들어가는 함수라고 생각하자는 것이다.
여기서 최솟값이 될 수 있는 후보들을 추려보자. 그럼 초록색 선들만 남을 것이다.
그럼 최고점을 기준으로 함숫값이 왼쪽은 증가, 오른쪽은 감소하는 형태로 있기 때문에 이분 탐색을 통해 \(O(\log N)\)만에 최솟값을 찾을 수 있다.
이제는 구현을 해야 한다. 구현을 할때 어차피 b가 감소하니까 함수들을 하나씩 볼 때 기울기가 감소하는 형태로 들어온다. 그러니 진짜 볼록 껍질을 만들듯이 스택에 교점들을 하나씩 집어넣되, 모노톤을 유지하면서 집어넣으면 된다. 마치 볼록 껍질을 찾듯 새로 구한 교점이 더 작으면 그걸로 교체해주면 된다.
예를 들어 이런 모양을 만드려면
여기까진 그냥 해주면 되고
마지막 선을 넣을 때 x좌표가 더 작은 교점이 나왔으니까 더 작은 교점으로 바꿔주면 된다. 그리고 저 두 교점이 한 스택에 담겨있으니까 교점들을 이분탐색하며 찾고자 하는 좌표가 어느 선분 위에 있는지를 찾으면 된다.
4008번: 특공대
입력은 세 줄로 구성된다. 첫 번째 줄에 전체 병사들 수인 양의 정수 n이 주어진다. 두 번째 줄에 특공대의 조정된 전투력 계산 등식의 계수인 세 정수 a, b, c가 주어진다. 마지막 줄에 병사들 1, 2,
www.acmicpc.net
이 문제를 보자. 이 문제는 나무 자르기랑 반대로 최댓값을 구하는 문제이다. 그럼 반대로 아래 그림처럼 함수들이 분포하게 될거고, 볼록 껍질도 아래로 볼록한 껍질을 잡아주면 된다.
라이님 블로그를 보면 전체적인 CHT의 설명과 특공대 문제의 풀이, a 배열이 증가하는 조건을 응용해서 \(O(N)\)으로 나무 자르기 문제를 푸는 풀이도 설명되어있으니 참고하자.
컨벡스 헐 트릭(Convex Hull Trick)
안녕하세요. 다시 DP입니다. 원래 확장 유클리드 알고리즘에 이어서 컨볼루션과 FFT를 쓰려고 했는데,...
blog.naver.com