알고리즘 테크닉 - 좌표 압축이란?

좌표 압축이란?

좌표 압축^{Coordinate Compression}은 일종의 테크닉이다. 배열이나 데이터 구조에서 사용되는 좌표값을 압축해 메모리를 절약할 수 있고, 알고리즘의 실행 속도를 향상시킬 수 있다는 이점이 있다. 주로 주어진 수에 비해 범위가 클 때 사용하는 테크닉이다.

좌표 압축 방법

좌표 압축의 주요 단계는 다음과 같다.

1. 중복 제거 주어진 좌표값 중 중복된 값들을 제거한다.
2. 정렬 남은 좌표값들을 정렬한다.
3. 압축된 좌표 값 부여 정렬된 좌표 값에 대해 각각 순서대로 압축된 값을 할당한다. 이렇게 되면 중복을 제거하고 연속적인 정수로 좌표값을 나타낼 수 있게 된다.

예제를 하나 가져와서 설명해보도록 하겠다. 백준 18870번 문제: 좌표 압축의 ‘예제 입력 1’의 수를 가져와봤다.

$2, 4, -10, 4, -9$

1. 중복 제거 및 정렬 [ $2, 4, -10, 4, -9$ ]의 중복된 값을 제거하면 [ $2, 4, -10, -9$ ]가 되고, 이 수를 오름차순으로 정렬하면 [ $-10, -9, 2, 4$ ]이 된다.

2. 압축된 좌표 값 부여 이제 순서대로 인덱스를 부여해준다. [ $-10, -9, 2, 4$ ]에서 순서대로 인덱스를 부여하면 [ $(-10,0), (-9,1), (2, 2), (4, 3) $ ]이 된다.

3. 압축된 값을 원래의 좌표 값으로 대체 이렇게 부여된 인덱스를 원래의 좌표 값에 넣어준다. [ $2, 4, -10, 4, -9$ ] 에서 인덱스를 넣어주면 최종 값은 [ $2, 3, 0, 3, 1$ ]이 된다.

알아두면 좋은 정보

1. 주어진 수가 N개이면, 좌표 압축한 수 또한 N개이다
2. 좌표 압축의 시간복잡도는 $O(nlogn)$이다.
3. 주어진 배열을 펜윅 트리(Fenwick Tree)나 세그먼트 트리(Segment Tree)의 인덱스로 사용할 때 사용할 수 있다.

보통 세그트리나 오프라인 쿼리등을 처리할 때 등등 많은 경우에 사용하는 유용한 테크닉이다.