좌표 압축

좌표 압축이란?

좌표 압축(coordinate compression) 은 실제 값의 크기는 크지만 종류는 적을 때,
각 값을 정렬 순서(등수) 로 바꿔 작은 범위로 옮기는 전처리 기법입니다.

값이 \(10^9\)까지 가더라도 서로 다른 값이 \(N\)개(\(\le 10^5\))뿐이라면, 그 값들을
\(0, 1, 2, \dots, N-1\)로 다시 매겨도 대소 관계는 그대로 유지됩니다.

1. 왜 필요한가

세그먼트 트리, 누적 합, 배열 카운팅 같은 많은 기법은 값을 배열의 인덱스로
씁니다. 그런데 값이 \(10^9\)까지면 그 크기의 배열을 만들 수 없습니다(메모리 초과).

좌표 압축은 "값의 실제 크기는 중요하지 않고 상대적 순서만 중요하다"는 점을
이용해, 값들을 \(0 \sim N-1\) 범위로 눌러 배열 크기를 \(O(N)\)으로 줄입니다.

원래 값: [100, 50000, 7, 100, 99999999]
서로 다른 값 정렬: [7, 100, 50000, 99999999]
압축 결과: [1, 2, 0, 1, 3]   (각 값의 등수)

2. 핵심 절차

좌표 압축은 세 단계로 끝납니다.

1. 모든 값을 모아 정렬한다.
2. 중복을 제거한다(서로 다른 값만 남김).
3. 각 원래 값을, 정렬된 목록에서의 위치(인덱스) 로 바꾼다 — 이분 탐색으로
   위치를 찾음.

대소 관계가 보존되므로, 압축 전후의 정렬·비교 결과가 동일합니다.

3. 복잡도

정렬 \(O(N \log N)\), 중복 제거 \(O(N)\), 각 값의 위치 찾기 \(O(\log N)\). 전체
\(O(N \log N)\)입니다. 이 한 번의 전처리로 이후 알고리즘이 작은 배열에서
동작할 수 있게 됩니다.

4. 대표 활용

특히 "값이 \(10^9\)인데 세그먼트 트리/펜윅을 쓰고 싶다"면 거의 항상 좌표 압축이
먼저 옵니다.

5. 주의: 순서만 보존, 거리는 잃는다

좌표 압축은 대소 관계만 보존합니다. 값들 사이의 실제 차이(거리) 는
사라집니다. 그래서 "두 값의 차"나 "구간의 실제 길이"가 필요한 문제에는
그대로 쓰면 안 됩니다 — 등수가 아니라 원래 값을 따로 보관해야 합니다.

정리

좌표 압축은 "값을 등수로" 바꿔 큰 값 범위를 \(O(N)\) 인덱스로 줄이는 전처리입니다.
정렬 → 중복 제거 → 이분 탐색으로 위치 찾기, 이 세 단계가 전부입니다. 세그먼트
트리·펜윅·카운팅의 단골 짝꿍입니다. 다음 강의에서 구현합니다.

좌표 압축을 코드로

표준 구현과 역방향 복원, 그리고 대표 응용(역순쌍 카운팅)을 다룹니다.

1. 표준 구현

#include <algorithm>
vector<int> a(n);                       // 원래 값들
// 1) 값 모으기 + 정렬 + 중복 제거
vector<int> sorted_vals(a);
sort(sorted_vals.begin(), sorted_vals.end());
sorted_vals.erase(unique(sorted_vals.begin(), sorted_vals.end()),
                  sorted_vals.end());
// 2) 각 값을 등수로 변환 (이분 탐색)
for (int i = 0; i < n; i++)
    a[i] = lower_bound(sorted_vals.begin(), sorted_vals.end(), a[i])
           - sorted_vals.begin();
// 이제 a[i]는 0 ~ (서로 다른 값 수 - 1) 범위

a = nums[:]
sorted_vals = sorted(set(a))            # 정렬 + 중복 제거
rank = {v: i for i, v in enumerate(sorted_vals)}   # 값 → 등수
a = [rank[x] for x in a]                # 압축

C++의 sort + unique + erase는 중복 제거의 표준 관용구이고, 파이썬은
sorted(set(...)) + 딕셔너리 한 줄로 끝납니다.

2. 역방향 복원

압축한 등수를 다시 원래 값으로 되돌리려면 정렬된 배열을 인덱스로 참조합니다.

int original = sorted_vals[compressed];   // 등수 → 원래 값

original = sorted_vals[compressed]

원래 값이 필요한 출력 단계에서 이 복원을 씁니다.

3. 응용: 역순쌍(inversion) 카운팅

"\(i < j\)인데 \(a[i] > a[j]\)인 쌍의 수"를 펜윅 트리로 구할 때, 값이 크면 좌표
압축이 필수입니다.

// a를 좌표 압축한 뒤 (값이 0 ~ m-1):
long long inv = 0;
vector<int> bit(m + 1, 0);              // 펜윅 트리
auto update = [&](int i){ for (i++; i <= m; i += i & -i) bit[i]++; };
auto query  = [&](int i){ int s=0; for (i++; i>0; i-=i&-i) s+=bit[i]; return s; };
for (int j = n - 1; j >= 0; j--) {
    inv += query(a[j] - 1);             // 뒤에 있으면서 나보다 작은 값의 수
    update(a[j]);
}

값이 \(10^9\)여도 압축 후 펜윅 크기는 \(O(N)\)이라 동작합니다.

4. 응용: 큰 격자의 좌표 압축

평면에 점이 \(N\)개 있고 좌표가 \(10^9\)급이면, 등장하는 x좌표끼리, y좌표끼리
따로 압축해 \(N \times N\) 격자로 만든 뒤 처리합니다. 직사각형 영역 합/이벤트
스위핑에 자주 쓰입니다.

5. 흔한 실수

• 중복 제거 빠뜨림 — unique/set 없이 압축하면 같은 값이 다른 등수를 받아
  대소 관계가 깨집니다.
• 거리 정보 손실 간과 — 등수는 실제 값의 차이를 보존하지 않음. 차이가
  필요하면 원래 값을 따로 보관.
• unique 전 정렬 누락 — C++ unique는 정렬된 배열에서만 인접 중복을
  제거합니다.
• 0-인덱스/1-인덱스 혼동 — 펜윅 트리는 보통 1-인덱스라 +1 처리 필요.
• 이분 탐색 대상 — 반드시 정렬·중복 제거된 배열에 lower_bound.

6. 패턴 알아보기

• "값이 \(10^9\)인데 세그먼트 트리/펜윅/카운팅 배열을 쓰고 싶다" → 좌표 압축.
• "역순쌍/순위/k번째 수" → 압축 + 펜윅.
• "큰 좌표 평면의 영역 질의" → x, y 각각 압축.
• 단, "값의 실제 차이"가 필요하면 등수만으로는 안 됨.

실전에서 좌표 압축 문제 알아보기

좌표 압축은 단독 문제보다 "이걸 안 하면 다음 단계가 불가능한" 전처리로
등장합니다. 언제 필요한지, 무엇을 압축 대상에 넣어야 하는지를 다룹니다.

1. 출제 신호

• 값의 범위는 \(10^9\)인데 개수는 \(N \le 10^5\) — 이 격차가 핵심 신호입니다.
  값으로 배열 인덱스를 만들 수 없지만, 서로 다른 값은 최대 \(N\)개입니다.
• "몇 번째로 작은 값인가", "자기보다 작은 값의 개수" — 등수 자체가 답.
• 값을 배열 인덱스로 써야 하는 후속 기법 — 체크 배열, 빈도 배열,
  (Gold 이후) 펜윅 트리. "값 기준 집계"가 보이면 압축부터 떠올리세요.
• 수직선 위의 좌표·구간 끝점이 크고 희소할 때 — 이벤트가 있는 지점만
  남기고 줄입니다.

2. 풀이 결정 절차

1. 압축 대상 값을 전부 수집합니다 — 배열 원소만이 아니라 쿼리에
   등장하는 값, 구간의 양 끝점까지. 나중에 변환할 값이 사전에 없으면
   끝장입니다.
2. 정렬 + 중복 제거로 사전을 만듭니다.
3. 이분 탐색(lower_bound/bisect_left) 으로 값 → 등수 변환 함수를
   만듭니다.
4. 결과 출력에 원래 값이 필요한지 확인합니다 — 필요하면 사전(등수 →
   값)을 역참조용으로 보관합니다.

3. 자주 하는 실수

• C++에서 unique 후 erase 누락. unique는 중복을 뒤로 밀 뿐 지우지
  않습니다. 꼬리를 잘라야 사전이 완성됩니다.

vector<int> v(a);                       // 원본 보존, 사본으로 사전 제작
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());   // erase까지가 한 세트
int rank_of_x = lower_bound(v.begin(), v.end(), x) - v.begin();  // 0-기준 등수

• 쿼리 값 수집 누락. 배열에는 없고 쿼리에만 나오는 값을 사전에 안 넣으면
  lower_bound가 엉뚱한 등수를 줍니다. "변환할 모든 값"을 처음에 한 번에
  모으세요.
• 중복 제거 여부와 의미 혼동. "자기보다 작은 서로 다른 값의 개수"는
  중복 제거 후 lower_bound, "작은 원소의 개수"는 중복 제거 없이
  정렬 배열에 lower_bound입니다. 문제가 어느 쪽인지 먼저 판정하세요.
• 파이썬에서 매 변환마다 list.index 사용. \(O(N)\) 검색이라 전체
  \(O(N^2)\)이 됩니다. {값: 등수} 딕셔너리를 한 번 만들거나 bisect_left를
  쓰세요.
• 원본 배열을 정렬해 버림. 출력은 입력 순서대로인데 원본을 제자리
  정렬하면 복구가 안 됩니다. 사전은 반드시 사본으로 만드세요.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 순 → 어려운 순입니다. 순수 등수
변환부터, 압축 후 빈도 배열·체크 배열로 이어지는 결합 문제로 올라갑니다.

문제마다 "압축 대상 값의 목록(배열? 쿼리? 끝점?)"을 먼저 적는 습관이
누락 실수를 막아 줍니다. 3문제 이상 풀어 클리어하면 레이팅의
CLASS 보너스에 반영됩니다. 좌표 압축은 Gold의 펜윅 트리·스위핑에서
계속 쓰이는 필수 전처리입니다.