목록2026/02/23 (1)
Elevation
볼록 껍질을 이용한 최적화 (Convex Hull Trick)
볼록 껍질을 이용한 최적화, 혹은 컨벡스 헐 트릭(CHT)은 위 그림처럼 여러 직선이 주어져 있을 때, 직선이 이루는 볼록 껍질을 구하여 x에 따른 최솟값을 구하는 최적화 기법이다. 따라서 평소라면 $O(n)$이 걸릴 최솟값 문제를, x가 속한 구간만 이분 탐색으로 찾으면 되므로 $O(\log n)$에 해결할 수 있게 된다. cht는 dp가 아니어도 충분히 사용될 수 있지만 dp의 최적화 기법으로도 자주 사용되기에 dp 카테고리에 작성하였다. cht를 적용하려면 다음과 같은 조건이 필요하다. 일차 함수 관계이거나, 일차 함수 형태로 변형 가능한 문제여야 한다.직선들이 볼록 껍질을 구성해야 하므로, 그 기울기가 단조 증가 혹은 감소해야 한다. (ex. 양수로 구성된 배열의 누적합) 컨베이어 벨트 (BOJ ..
ps/dp
2026. 2. 23. 19:50