값 / 좌표 압축 (Coordinate Compression) 은 큰 범위의 값 (예: 10^9) 을 정렬된 순서를 유지하며 작은 정수 인덱스 (0..K-1) 로 매핑하는 기법. K = unique value count.
문제 상황과 동기
값의 범위가 10^9 이고 입력 크기가 10^5 라면, Fenwick tree 나 segment tree 를 값 자체를 인덱스로 사용할 수 없음. 압축하면 희소한 값들을 연속된 인덱스로 바꾸어 배열 기반 자료구조를 사용 가능.
핵심 통찰: 상대 순서만 중요하지 절대값은 중요하지 않다. 값을 정렬하고 중복 제거한 뒤, 각 값의 순위(index)가 곧 압축된 좌표.
시각화
핵심 아이디어
1. unique = sort(unique(set(original))) // 정렬 + 중복 제거2. for each value v in original: compressed[v] = lower_bound(unique, v) // unique[compressed[v]] == v
압축 후에는 unique[compressed[i]] 로 원래 값을 복원 가능.
알고리즘
compress(a[]): sorted = sort unique values of a for each x in a: idx = lower_bound(sorted, x) print idx // 0-based compressed coordinate// 예: a = [-5, 10^9, 0, -5, 42]// sorted = [-5, 0, 42, 10^9]// compressed = [0, 3, 1, 0, 2]
구현
// Coordinate compression: O(N log N)#include <bits/stdc++.h>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (auto& v : a) cin >> v; // 1. Extract unique sorted values vector<int> uniq = a; sort(uniq.begin(), uniq.end()); uniq.erase(unique(uniq.begin(), uniq.end()), uniq.end()); // 2. Map each original value to compressed index for (auto& v : a) { v = (int)(lower_bound(uniq.begin(), uniq.end(), v) - uniq.begin()); cout << v << " "; } cout << "\n"; // Reconstruct original: uniq[compressed[i]] // for (auto v : a) cout << uniq[v] << " ";}
# Coordinate compression: O(N log N)import sysinput = sys.stdin.readlinefrom bisect import bisect_leftn = int(input())a = list(map(int, input().split()))# 1. Extract unique sorted valuesuniq = sorted(set(a))# 2. Map each value to compressed indexcompressed = [bisect_left(uniq, v) for v in a]print(*compressed)# uniq[compressed[i]] == original a[i]
// Coordinate compression: O(N log N)import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] a = new int[n]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); // 1. Extract unique sorted values int[] sorted = a.clone(); Arrays.sort(sorted); int k = 1; for (int i = 1; i < n; i++) if (sorted[i] != sorted[k - 1]) sorted[k++] = sorted[i]; // 2. Binary search for compression StringBuilder sb = new StringBuilder(); for (int v : a) { int idx = Arrays.binarySearch(sorted, 0, k, v); sb.append(idx).append(' '); } System.out.println(sb); }}
stdin
7-5 1000000000 0 -5 42 999999999 0
결과
0 4 1 0 2 3 1
stdin
5100 200 300 400 500
결과
0 1 2 3 4
복잡도
항목
값
시간
O(N log N)
공간 (unique 배열)
O(K), K = unique value count
압축 크기
K ≤ N
복원 (index → value)
O(1), uniq[idx]
변형 / 활용
적용처
설명
Fenwick / Segment Tree
좌표 압축 후 값 범위가 10^9 → 10^5 로 축소
Mo’s algorithm
값 범위를 압축해 카운팅 배열 사용 가능
Sweeping
x, y 좌표를 각각 압축해 격자로 변환
LIS
음수/큰 값 좌표를 순위로 변환해 O(N log N) LIS
2D 압축
x, y 각각 압축해 희소 2D 그리드 구성
함정
1. 중복 제거 누락
unique() 또는 set() 으로 중복을 제거하지 않으면, 같은 값이 여러 인덱스를 가져 Fenwick 트리에서 overflow / 잘못된 결과.
2. lower_bound 대신 map 사용
Python 의 dict 나 C++ 의 unordered_map 을 쓰면 O(1) mapping 이 가능하지만, 순서가 필요한 경우 (구간 쿼리, Fenwick) 는 정렬 배열 + binary search 가 필수.
3. 0-based vs 1-based
Fenwick tree 는 1-based index 가 필요. 압축 결과가 0-based (lower_bound 기본) 이면 compressed[i] + 1 사용.
💬 댓글