Elevation

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

비트마스킹(bitmasking)은 기본적으로 이진수 표현을 활용해서 자료를 저장하는 기법이다. 컴퓨터는 기본적으로 이진수 단위로 연산하다 보니 비트마스킹을 활용하면 메모리와 시간의 절약이 가능하다. 가령 0과 1로만 이루어진 자료를 표현할 때, [0, 1, 1, 0, ...]처럼 정수의 배열로 표현하는 것보다는, 0110...(2)로 묶어 하나의 정수로 담으면 더 효율적일 것이다. 다만 ps에서 비트마스킹이 필수일 정도로 시간/공간복잡도가 빡빡한 문제는 많지는 않다. 대신 이렇게 비트필드를 이용하면 자료를 하나의 수로 표현할 수 있음을 이용해, 서브 문제의 상태를 비트마스킹하여 dp 배열에 저장하는 방식으로 문제를 푸는 기법이 있다. 이를 비트필드를 이용한 DP라고 한다. 외판원 순회 문제(TSP)TS..