알고리즘/DP
2021. 11. 7.
Convex Hull Trick
DP 테이블의 각 값을 계산하는데, DP 테이블(또는 다른 배열)의 연속된 값들의 단순 연산 값이 필요하다면 누적합이나 Segment Tree등을 이용해 최적화 할 수 있다는 말을 전 글에서 설명한 바 있습니다. https://anz1217.tistory.com/130 기초 DP 최적화 DP를 최적화 하는 방법들에 대해 알아봅시다. https://anz1217.tistory.com/19 동적 계획법 (Dynamic Programming) 동적 계획법 (이하 DP)은 큰 문제를 분할하여 부분 문제들로 만든 다음, 각 부분 문제의 답으로.. anz1217.tistory.com 하지만 더 복잡한 수식을 계산한 값이 필요하다면 어떻게 해야 할까요? DP를 최적화하는 방법 중 하나인 Convex Hull Tric..
