Convex Hull Trick (1) 썸네일형 리스트형 197. Convex Hull Trick 이제부터는 여러 가지 DP 최적화(DP Optimization) 방법에 대해서 알아보기로 한다. DP 최적화는 DP 식이 특수한 형태로 존재할 때 그 식의 특성을 이용해서 시간복잡도를 줄이는 기법들을 의미한다. 그중 가장 먼저 살펴볼 내용은 컨벡스 헐 트릭(Convex Hull Trick, CHT)이며, DP 식이 다음과 같은 형태일 때 사용할 수 있다($\min$ 대신 $\max$가 들어갈 수도 있고 이 경우 $a_i$의 부등호 방향이 반대로 변함):$$S_i = \min_{j $$a_1 > a_2 > \ldots > a_{n - 1} > a_n$$이 식에서 $S_n$을 구하는 것이 목표라고 하면, $S_n$을 구하기 위해서는 $S_1$부터 $S_{n - 1}$까지를 모두 알아야 하는데 $S_1$부터 .. 이전 1 다음
