Table of Contents 개요 풀이 구현 더 알아보기 : 공간 복잡도 최적화 1. 개요 냅색 문제 ( 배낭 문제 ) 는 프로그래밍계에서 유명한 문제로서 요약하면, 담을 수 있는 무게의 최댓값이 있는 배낭, 그리고 무게와 가치를 가진 짐들이 있을 때 배낭에 넣을 짐들의 가치가 최대가 되도록 배낭에 넣을 짐들을 고르는 문제입니다. 이 문제는 짐을 쪼갤 수 있는 경우와 쪼갤 수 없는 경우로 나뉩니다. 이 중 쪼갤 수 없는 경우는 0/1 배낭 문제 ( 0/1 knapsack problem ) 이라고 불리며 동적 계획법으로 해결이 가능합니다. 아래의 링크를 통해 0/1 배낭 문제의 예시를 보고 코딩한 후, 채점해 볼 수 있습니다. 아래의 풀이와 구현은 이 문제를 기준으로 설명하므로 반드시 읽어보시길 바랍니..
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] 또한 상수입니다. 그러므로 위의 함수..
일단 마지막 계단까지 올라가는 최댓값을 구해야 하고 계단은 한번에 1개 혹은 2개를 올라갈 수 있으니 아래와 같이 설정해 볼 수 있다. DP( i ) = i번째 계단까지 올라가는 최댓값하위 문제 : DP( i-1 ), DP( i-2 ) 이 때, 아래에 있는 계단으로 갈 수가 없으니 사이클이 생길 일에 대해선 걱정할 것이 없다. 하지만 ‘연속된 세 개의 계단을 모두 밟아서는 안 된다. ’는 조건이 있는데 이를 DP( i-1 ), DP( i-2 )의 정보만 가지고는 처리를 할 수 없으므로 DP 설정에 정보를 추가해야 한다. DP( i, j ) = 마지막 점프가 j 개를 올라가는 점프일 경우, i 번째 계단까지 올라가는 최댓값하위 문제 : DP( i-1, 2 ), DP( i-2, 1 ), DP( i-2, 2 ..