Table of Contents 개요변환1차 함수 집합 관리최소값 찾기문제 1. 개요 컨벡스 헐 트릭 ( Convex hull trick, Convex hull optimization)은 동적 계획법에서 특정 형태의 점화식이 사용되었을 시 시간복잡도를 획기적으로 줄여주는 기법입니다. DP 관계식을 아래와 같이 정리 가능할 때 사용할 수 있습니다. D[i] 는 어차피 j와 상관이 없기 때문에 상수처럼 취급하고, (i에 대한 함수) * (j에 대한 함수) + (j에 대한 함수) 으로 생각하면 쉽게 컨벡스 헐 트릭의 모양이란 걸 알 수 있습니다. 2. 변환 우선 각각의 j 에 대해 다음과 같은 함수를 생각해봐야 합니다. 여기에서 j 는 정해진 상수이므로 B[j], C[j] 또한 상수입니다. 그러므로 위의 함수..
Table of Contents 개요 DP 기본 예제 – 피보나치 수열 DP 구현하기 DP 문제 - 1 DP로 문제에 접근하기 DP 문제 - 2 유명한 DP 응용 주의할 점 DP 문제 - 3 1. 개요 동적 계획법, 영어로 Dynamic programming 다이나믹 프로그래밍, 줄여서 DP. 문제를 여러 개의 하위 문제들로 나누어 먼저 처리한 후, 그 하위 문제들의 답을 이용해 원래 문제를 처리하는 방법을 뜻합니다. 하위 문제를 처리하는 과정에서 같은 문제를 여러 번 처리하게 되는데, 한 번 수행한 문제들의 답을 저장해 놓으면 그 다음부터는 답을 바로 알아낼 수 있어 속도를 비약적으로 빨라지게 할 수 있습니다. 2. DP 기본 예제 – 피보나치 수열 피보나치 수열을 DP로 구하는 과정을 통해서 DP에 ..