좌표 압축 알고리즘 이란?

백준 18870번 좌표압축문제를 풀려고 하다가, 일단 좌표압축의 개념부터 알아야 할 것 같아서 정리해본다.

 

좌표 압축 알고리즘이란?

: 모든 구간이 아니라, 중요한 구간이나, 숫자만 들고있는 기법.

→ 순위가 중요한 알고리즘에서 입력값의 개수 < 입력값의 범위일때 사용한다.

 

값보다 값의 순위가 중요하기 때문에, 값을 임의의 값으로 변경하되 순위만 유지하여도 문제를 풀 수 있도록 만드는 것이다.

 

예시로는 카카오 코드 페스티벌 5번 캠핑 문제가 있는데,

이 경우 좌표 x,y의 범위는 0 ~ 2^31-1 이지만, 입력받는 좌표의 개수는 최대 5000개이다.

 

만약 입력의 좌표를 그대로 반영하여 문제를 푼다고 하면 배열의 크기가 2^31-1 개가 되어야하며, 2차원이기 때문에 탐색에 너무 많은 시간이 들게 된다. 하지만 값보다 입력의 순위를 먼저하여, 입력의 최대의 개수인 최대 5000에 맞추어 좌표압축하여 입력받은 좌표를 0~5000 으로 매치시키고 풀게 되는 것이다.

 

따지자면 원래 있는 값에 좌표마다 indexing하여서 정렬된 순서대로 값을 매긴다고 봐도 좋을 것 같다.