Coordinate Compression 연구일지

Coordinate Compression이란

1차원 직선상에 N개의 점(1 <= N <= 10^5)이 있고, [x, y] 사이에 점 개수를 출력하는 쿼리가 있다면 Segment Tree를 구성하여 각 구간 사이에 몇 개 의 점이 있는지를 저장하여 쿼리를 처리하면 될 거 같습니다.

점의 범위가 [1, 10^5] 일 때는 어떨까요 O(log(10^5))이기 때문에 별 무리 없이 처리할 수 있습니다.

 

허나, 범위가 [-10^9, 10^9]라면 어떨까요 거의 int형의 MAX범위만큼 배열을 할당해야 하는데 메모리 때문에 대부분 문제에서 메모리 초과가 걸릴 겁니다.

 

방금 같은 상황에 예제를 하나 던져보겠습니다.

arr = {2, 30, 10000, 2, -100000}, 다음과 같은 점의 정보들을 담고 있는 arr가 있다고 합시다.

그럼 최솟값이 -100000, 최댓값이 10000이므로 최소한 110001 구간을 다루는 Segment Tree를 구성해야 합니다.

여기서 우리가 배우려는 Coordinate Compression을 사용해보자고요.

 

arrComp = {1, 2, 3, 1, 0}, 다음과 같이 좌표를 압축시킬 수 있습니다.

범위가 0~3, 크기가 4로 110001에서 확 줄어든 것을 확인할 수 있습니다.

즉, Segment Tree에서 110001만큼 처리해야 하는 구간을 0~3으로 확 줄인 것입니다.

 

즉, Coordinate Compression은 주어진 데이터들 사이의 순위가 궁금한데 범위가 너무 커서 메모리의 크기 때문에 버거워지는 경우 자주 사용하는 테크닉입니다.

 

그럼 어떻게 사용하는지에 대해 알아봅시다.

들어가기 전, 필요한 함수는 sort, unique, lower_bound입니다.

 

sort, lower_bound는 이미 잘 알고 있기 때문에 넘어갑니다.

unique함수란 중복된 원소를 뒤로 쓰레기 값으로 보내버리는 역할을 하는 함수입니다.

그렇기 위해서는 원소들이 인접하여 중복되어있음을 알려주어야 하기 때문에 정렬이 되어있어야 합니다.

그래서 정렬 후, unique를 사용하여 뒤로 중복된 쓰레기 값들을 보내버리는 것입니다.

그리고 unique는 쓰레기 값이 시작되는 iterator를 반환하기 때문에 unique를 사용하고, 끝까지 erase를 사용하면 중복된 쓰레기 값들은 모두 지워집니다.

 

이렇게 사용합니다.

sort(temp.begin(), temp.end());
temp.erase(unique(temp.begin(), temp.end()), temp.end());

 

BOJ에 18840(좌표 압축) 문제로 예시를 다루어 보겠습니다.

배열은 2가지를 사용합니다.

하나는 값 그 자체로 데이터를 받아서 마지막에 압축된 값으로 변환할 배열: v

하나는 해당 값이 몇 번째 값인지를 알아낼 배열: temp

 

lower_bound를 사용하는 이유는 v[i]에 해당하는 값이 temp에서는 몇 번째 값인지 알기 위해서입니다.

그리고, 몇 번째인지가 정렬이 되어있고, 쓰레기 값들은 날렸기 때문에 압축된 값이라고 할 수 있습니다.

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

vector<int> v;
vector<int> temp;
int n;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int value; cin >> value;
        v.push_back(value); temp.push_back(value);
    }
    
    // 정렬이 되어있어야 unique 함수를 통해 중복된 값을 지울 수 있다.
    // unique함수는 중복된 값들은 전부 다 뒤로 보낸다.
    // 그리고, unique함수는 중복되는 값이 시작되는 index의 iterator를 반환하므로
    // 해당 iterator부터 끝까지 지워버리면 temp에는 값의 순서들만 남게된다.
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    
    // v[i]값이 temp에서 몇 번째 값인지를 binarySearch를 통해 찾아서
    // 해당 index를 리턴받아서 index(순서)를 압축된 값으로 쓴다.
    for(int i = 0; i < v.size(); i++){
        int index = lower_bound(temp.begin(), temp.end(), v[i]) - temp.begin();
        v[i] = index;
    }
    
    for(int i = 0; i < v.size(); i++) cout << v[i] << ' ';
    return 0;
}