가장 쉽게 설명하는 - 좌표 압축 (Coordinate Compression)

개요

좌표 압축, 혹은 값 압축(Coordinate Compression)은 데이터 범위가 매우 클 때 효율적으로 처리할 수 있게 해주는 최적화 기법입니다.
이름만 들으면 뭔가 기하학적인 지식이 필요할 것 같지만, 절대 그렇지 않습니다!

좌표 압축은 알고리즘이라기 보단, 데이터를 다루는 하나의 방법론에 가깝습니다.

일반적인 코딩 테스트에서 잘 출제되는 편은 아니지만, 대회에서는 상당히 자주 사용되는 기법입니다.

대소 관계만 파악하기

예를 들어, 다음과 같은 배열이 있다고 해봅시다.

• {-10,000,000, 1,000, 100, 5, 1, 10,000,000}

위 배열을 좌표 압축하게 된다면 아래와 같이 됩니다.

• {0, 4, 3, 2, 1, 5}

규칙이 보이시나요? 배열의 각 숫자는 그 숫자가 배열 내에서 몇 번째로 작은 값인지를 나타내는 인덱스로 바뀌었습니다.
수 자체에는 관심을 가지지 않고, 단순히 대소 관계에만 관심을 가질 수 있다면 이렇게 효과적으로 연산량을 줄일 수 있습니다.

unique와 lower_bound

vector<int> X_index = X;
sort(X_index.begin(), X_index.end());
X_index.erase(unique(X_index.begin(), X_index.end()), X_index.end());

18870 - 좌표 압축의 코드 일부분입니다.

먼저 좌표 압축의 결과를 저장할 벡터 X_index를 선언하였습니다.
그리고, 작은 값부터 0부터 시작하여 좌표 압축을 하기 위해 정렬을 수행하였습니다.

위 문제에서는 0으로 좌표 압축을 하였지만, 문제에 따라서는 다르게 적용해야 할 수도 있습니다.

그리고, 중복된 값을 제거하기 위해 unique와 erase 함수를 사용하였습니다.
중복된 값을 제거하지 않는다면 {2, 3, 3, 4}와 같은 배열이 {0, 1, 1, 2}가 되어야 하는데, {0, 1, 2, 3}이 되기 때문입니다.

for (int i : X) {
  cout << distance(X_index.begin(), lower_bound(X_index.begin(), X_index.end(), i)) << " ";
}

이어서 원본 원소들이 담겨 있는 배열 X를 탐색합니다.
C++에는 해당 원소가 얼마나 멀리 떨어져 있는지를 구해 주는 distance가 있습니다. 이것과 lower_bound를 활용하여 원본 원소가 몇 번째 인덱스에 있는지 출력합니다.

for (int i : X) {
  cout << lower_bound(X_index.begin(), X_index.end(), i) - X_index.begin() << " ";
}

distance 함수 없이, lower_bound로만 사용하여 구할 수도 있습니다. 인덱스를 구하는 방법은 다양합니다.

코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int N;
  cin >> N;
  
  vector<int> X(N);
  for (int &i : X) {
    cin >> i;
  }
  
  vector<int> X_index = X;
  sort(X_index.begin(), X_index.end());
  X_index.erase(unique(X_index.begin(), X_index.end()), X_index.end());
  
  for (int i : X) {
    cout << distance(X_index.begin(), lower_bound(X_index.begin(), X_index.end(), i)) << " ";
  }
  
  return 0;
}

해결할 수 있는 문제

주로 세그먼트 트리, 스위핑과 함께 사용됩니다.

BOJ 18870 - 좌표 압축

위 코드를 그대로 사용하면 됩니다.