알고리즘 문제를 풀다 보면 다음과 같은 아찔한 제약 조건을 마주할 때가 있습니다. "점의 개수 N은 10만 개입니다. 그런데 각 점의 x, y 좌표 범위는 -10억부터 +10억까지입니다." 만약 이 점들을 다루기 위해 크기가 20억인 배열(Array)을 만들거나 세그먼트 트리를 구축하려고 한다면, 수 기가바이트의 메모리를 잡아먹으며 즉각적으로 메모리 초과(MLE) 판정을 받게 될 것입니다. 실제 데이터(점)는 고작 10만 개뿐인데, 그들이 놀고 있는 운동장(좌표계)이 너무 넓어서 발생하는 낭비입니다. 이때 좌표들의 '절댓값'은 무시하고, 오직 점들 사이의 '상대적인 대소 관계(순위)'만 남겨서 0번부터 N번까지의 촘촘한 배열로 우겨 넣는 천재적인 테크닉이 있습니다. 이것이 바로 '좌표 압축(Coordinate Compression)'입니다.
1. 텅 빈 우주를 압축하라
예를 들어 좌표가 [1000000, 5, -999, 5, 20]이라고 가정해 보겠습니다. 이 숫자들의 실제 크기는 세그먼트 트리나 펜윅 트리로 구간합을 구할 때 전혀 중요하지 않습니다. 중요한 것은 -999가 제일 작고, 1000000이 제일 크다는 순서(Rank)입니다.
이를 0부터 시작하는 촘촘한 정수로 변환(압축)하면 [3, 1, 0, 1, 2]가 됩니다. 이제 우리는 -999부터 100만까지의 거대한 인덱스 공간 대신, 0부터 3까지의 아주 작고 귀여운 인덱스 공간만으로도 알고리즘을 완벽하게 수행할 수 있게 됩니다.
2. 좌표 압축의 3단계 완벽 구현 (O(N log N))
이 마법을 구현하는 코드는 정렬과 이진 탐색의 조합으로 매우 간단하게 작성됩니다.
1단계: 원본 복사 및 정렬
원본 배열을 훼손하면 안 되므로 복사본 배열을 하나 만듭니다. 그리고 복사본을 오름차순으로 정렬합니다.
복사본: [-999, 5, 5, 20, 1000000]
2단계: 중복 제거 (Unique)
순위를 매길 때 같은 값은 같은 순위를 가져야 하므로, 정렬된 배열에서 중복된 값을 깔끔하게 제거합니다. (C++의 std::unique, Java의 Set, Python의 set을 활용합니다.)
중복 제거 후: [-999, 5, 20, 1000000]
3단계: 이진 탐색으로 순위(Index) 매핑
이제 원본 배열을 순회하며, 원본의 각 숫자가 중복 제거된 배열에서 몇 번째 인덱스에 위치하는지를 찾아서 덮어씌웁니다. 정렬된 배열에서 값을 찾는 것이므로 이진 탐색(Lower Bound / Bisect)을 사용하면 단 O(log N) 만에 순위를 찾아낼 수 있습니다.
원본 1000000은 중복 제거 배열에서 3번 인덱스이므로 3으로 변환. 5는 1번 인덱스이므로 1로 변환.
3. 어떤 문제에서 진가를 발휘하는가?
좌표 압축은 주로 세그먼트 트리(Segment Tree)나 펜윅 트리(Fenwick Tree)와 결합될 때 진가를 발휘합니다. 범위가 10억인 2차원 평면에서 특정 직사각형 구간 안에 점이 몇 개나 들어있는지 세는 문제(2D 쿼리 문제)나 스위핑(Sweeping) 알고리즘을 쓸 때, 이 기법을 사용하지 않으면 자료구조 자체를 메모리에 올릴 수 없게 됩니다. O(N log N)의 짭짤한 투자로 메모리 제약을 분쇄해 버리는 알고리즘 세계의 압축 프로그램(ZIP)과 같은 존재입니다.
1. 좌표 압축(Coordinate Compression)은 좌표의 범위는 미친 듯이 크지만 실제 점의 개수는 적을 때, 절댓값을 버리고 상대적인 순위(0 ~ N)로 값을 치환하여 메모리 낭비를 막는 기법입니다.
2. 배열을 복사하여 정렬한 뒤 중복을 제거하고, 원본 값들이 새 배열에서 몇 번째 위치인지 이진 탐색(Lower Bound)으로 찾아 덮어씌우는 방식으로 O(N log N)에 구현됩니다.
3. 인덱스의 범위가 곧 메모리 공간이 되는 세그먼트 트리나 구간합 문제에서 메모리 초과(MLE)를 회피하기 위한 가장 완벽한 전처리(Preprocessing) 기술입니다.