---
id: "lessons/coordinate-compression"
title: "좌표 압축: 순서는 남기고 값의 크기는 줄이기"
description: "큰 값과 중복을 작은 인덱스로 바꾸고, 순위 차이와 실제 거리의 차이를 확인합니다."
kind: "record"
published: "2026-10-04T00:00:00.000Z"
tags: ["알고리즘","C++","자료구조"]
url: "https://www.readiz.com/records/coordinate-compression/"
markdownUrl: "https://www.readiz.com/records/coordinate-compression/index.md"
---

# 좌표 압축: 순서는 남기고 값의 크기는 줄이기

값이 1조여도 서로 다른 값이 몇 개 없다면, 그 값들을 작은 배열의 인덱스로 바꿀 수 있습니다. 단, 압축한 인덱스는 순위를 나타낼 뿐 원래 거리를 나타내지는 않습니다. 이 구분을 손으로 확인하고, 중복과 음수가 있는 입력을 실행합니다.

좌표 압축은 값의 크기 자체는 크지만 서로 다른 값의 개수가 작을 때, 값을 `0..m-1` 또는 `1..m` 범위의 인덱스로 바꾸는 기법입니다. Fenwick Tree, Segment Tree, 스위프 라인, 오프라인 쿼리에서 자주 함께 쓰입니다.

## 값은 크지만 서로 다른 값의 개수는 작을 때

예를 들어 좌표가 `1`, `1,000,000,000`, `500,000,000`처럼 크면 좌표를 그대로 배열 인덱스로 쓸 수 없습니다. 하지만 실제로 등장한 값이 3개뿐이라면, 정렬 순서만 유지해서 아래처럼 바꿀 수 있습니다.

```text
원래 값: 1, 500000000, 1000000000
압축 값: 0, 1, 2
```

중요한 것은 **대소 관계를 보존한다**는 점입니다. 원래 값이 작을수록 압축 인덱스도 작습니다.

## 정렬 + unique

먼저 모든 값을 한 벡터에 모아 정렬하고 중복을 제거합니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp
vector<int> values = a;
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
```

이제 `values[i]`는 압축 인덱스 `i`가 나타내는 원래 값입니다.

## lower_bound로 압축 인덱스 만들기

원래 값 `x`의 압축 인덱스는 `lower_bound`로 찾습니다.

```cpp
int compress(const vector<int>& values, int x) {
    return lower_bound(values.begin(), values.end(), x) - values.begin();
}
```

모든 `x`가 `values`에 들어 있다는 전제가 있어야 합니다. `lower_bound`는 없는 값에도 삽입 위치를 반환하므로, 끝에 도달했는지와 실제 값이 `x`인지 구분합니다. 온라인으로 새로운 값이 중간에 들어오는 문제라면, 먼저 모든 쿼리를 읽어 등장 가능한 값을 모으는 오프라인 처리가 필요할 수 있습니다.

## 압축부터 복원까지 따라가기

[정렬·중복 제거·순위 매핑 실험](https://www.readiz.com/learn/explore/?demo=compression)

입력 `[-10, 100, -10, 7, 100, 8]`을 정렬하면 `[-10, -10, 7, 8, 100, 100]`, 중복을 없애면 `[-10, 7, 8, 100]`입니다. 원래 순서에서 각각의 위치를 찾으면 `[0, 3, 0, 1, 3, 2]`가 됩니다. 같은 값은 같은 인덱스를 공유하지만, 입력 원소 자체를 삭제하지는 않습니다.

![원래 값 10,20,100은 순위 0,1,2가 됩니다. 순위 간격은 둘 다 1이지만 실제 구간 길이는 10과 80입니다. 원래 값 배열을 보관해야 길이를 복원할 수 있습니다.](https://www.readiz.com/assets/lessons/range-structures/compression-gaps.svg)

[그림 크게 보기](https://www.readiz.com/assets/lessons/range-structures/compression-gaps.svg)

작은 순위만 저장해도 되는 빈도·대소 비교와, 원래 간격이 필요한 길이·넓이 계산을 구분하세요. 압축한 두 구간을 각각 길이 1로 세면 전체 길이를 2로 계산하지만, 원래 `[10,100)`의 길이는 90입니다.

**정수 범위도 함께 옮겨야 합니다.** 위 개념 조각은 `vector<int>`이지만 아래 연습은 절댓값 `10^12`까지 받습니다. 다운로드 예제에서는 원본 값과 중복 제거 배열을 `long long`으로, 압축 인덱스를 `int`로 저장합니다.

## 압축한 값을 빈도 인덱스로 쓰기

역전쌍은 `i < j`인데 `a[i] > a[j]`인 쌍입니다. 왼쪽부터 읽으면서 [Fenwick Tree](https://www.readiz.com/records/fenwick-tree/)에 값별 등장 횟수를 저장하면 셀 수 있습니다.

현재 값의 0-based 압축 인덱스가 `r`이고 앞에서 `i`개를 읽었다면, 1-based Fenwick에서 새 역전쌍은 `i - prefixSum(r + 1)`개입니다. `prefixSum(r + 1)`는 현재 값 **이하**의 개수이므로 같은 값끼리는 세지 않습니다. 답에 더한 뒤 `add(r + 1, 1)`로 빈도를 1 올립니다.

`[3, 1, 3, 2]`를 읽으면 새로 생기는 쌍은 차례로 `0, 1, 0, 2`개, 총 3개입니다. 압축 순위와 Fenwick 인덱스 사이의 `+1`을 질의와 갱신 양쪽에 적용합니다.

## 구간 좌표 압축에서 주의할 점

[원문의 구조 그림 크게 보기](https://www.readiz.com/assets/lessons/range-structures/coordinate-compression-original.svg)

`[10,20)`과 `[20,100)`은 압축 후 각각 한 칸이지만 길이는 10과 80입니다. 길이·넓이를 합산할 때는 원본 좌표 간격을 함께 저장합니다.

구간 `[l, r]`을 다룰 때는 문제의 의미에 따라 `r + 1`도 같이 넣어야 할 수 있습니다. 예를 들어 차분 배열처럼 `[l, r]`에 더하고 `r + 1`에서 빼는 방식이면 `r + 1` 좌표가 반드시 필요합니다.

또 면적이나 길이를 계산하는 문제에서는 압축 인덱스 차이가 실제 거리와 다릅니다. 이때는 `values[i + 1] - values[i]`처럼 원래 좌표 간격을 곱해야 합니다.

## 시간 복잡도

| 작업                    | 시간           |
| --------------------- | ------------ |
| 값 수집                  | `O(n)`       |
| 정렬과 중복 제거             | `O(n log n)` |
| 값 하나 압축               | `O(log n)`   |
| unordered map으로 미리 매핑 | 평균 `O(1)`    |
| 메모리                   | `O(n)`       |

## 로컬 연습: 중복과 음수가 있는 값의 순위

서로 다른 값을 정렬한 뒤 각 원소를 그 배열에서의 0-based 위치로 바꾸세요. 압축값의 차이가 실제 거리라고 가정하지 않습니다.

**입력:** N과 길이 N의 정수 배열. 1 <= N <= 200000, |a\[i]| <= 10^12입니다.

**출력:** 첫 줄에 서로 다른 값의 수, 둘째 줄에 원래 순서의 압축값, 셋째 줄에 정렬된 서로 다른 원본 값을 출력합니다.

### 예시

```text exercise=coordinate-compression role=input
6
-10 100 -10 7 100 8
```

```text exercise=coordinate-compression role=output
4
0 3 0 1 3 2
-10 7 8 100
```

**확인 방법:** 원본의 같음·대소 관계가 압축값에서도 유지되고 coords\[rank\[i]]가 a\[i]로 복원되는지 확인합니다. 전부 같은 값, 감소 순서, 64비트 값을 검사합니다.

## 완성 파일로 실행하고 확인하기

[C++17 전체 예제 내려받기](https://www.readiz.com/assets/lessons/range-structures/coordinate-compression.cpp)

```sh
c++ -std=c++17 -O2 coordinate-compression.cpp -o lesson
./lesson < input.txt
```

원본 값은 64비트 정수, 순위는 0-based입니다. 위 예제의 세 줄을 그대로 출력합니다. 파일은 정렬과 중복 제거, 순위 조회를 `compressValues` 함수로 묶고 `main`까지 포함합니다.

입력 `[-1000000000000, 1000000000000, -1000000000000]`이면 서로 다른 값은 2개, 순위는 `[0,1,0]`입니다. 값이 모두 같으면 모두 0이 됩니다. 출력한 원본 값 배열 `coords`를 사용해 모든 위치에서 `coords[rank[i]] == input[i]`가 성립하는지 확인하세요. 이 검사는 순서와 중복 처리를 함께 확인합니다.

[Fenwick Tree](https://www.readiz.com/records/fenwick-tree/)와 연결할 때는 압축 순위에 1을 더해 호출합니다. 역전쌍에서 같은 값을 제외하려면 ‘현재 값 이하’의 개수를 빼야 한다는 점도 확인하세요. 압축이 실제 값의 중복까지 없애 주는 것은 아닙니다.