Elevation

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

CCW(Counter Clockwise)란 세 점의 진행 방향이 시계 반대 방향인지, 시계 방향인지 판단할 수 있게 해 주는 알고리즘이다.$CCW(A, B, C)$는 세 점을 입력으로 받아 직선 $AB$와 점 $C$의 위치 관계를 판단한다. $C$가 직선 $AB$에 비해 반시계 방향으로 진행한다면 양수를, 시계 방향으로 진행한다면 음수를, 직선 위에 있다면 0을 반환한다. CCW 알고리즘은 벡터의 외적을 활용한다. 두 벡터 $\overrightarrow{AB}$와 $\overrightarrow{AC}$를 외적하면 그 부호는 오른손 법칙에 의해 결정되는 외적의 방향을 의미한다. $\overrightarrow{AB}$에 비해 $\overrightarrow{AC}$가 시계 반대 방향이라면 외적은 2차원 평면을..

4단계를 다 풀었다. 난이도는 실버 상위~골드 하위 수준이고 dp, 그래프 탐색, 백트래킹, 구현 위주의 문제가 많았다. 한문제씩 풀 때는 그렇게 오랜 시간이 걸리지 않았는데, 확실히 정해진 48문제를 다 푸는 것은 마냥 쉽지는 않은 것 같다. 푼 문제 수가 늘어갈수록 남아있는 문제들은 더 까다롭게 다가오는 느낌이었다. 아이디어가 떠오르지 않아서 자력으로 푸는 데 꽤 많은 시도를 한 문제들도 있었다. 아무튼 이번에 새로 배웠거나 헷갈리는 개념(문제)들 위주로 간단히 정리해 본다. LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)LIS 자체는 dp로 $O(N^2)$만에 해결 가능하다. 수열 $A$에 대해 $dp[i]$=($A[i]$까지의 LIS)라고 생각하면,..