Live of Thinking

좌표 압축(Coordinate Compression)^[각주:1]은 범위가 큰 값들을 처리하기 위해 값들을 치환하여 범위를 줄이는 기법이다. 이 방법을 적용하기 위해서는 상대적인 값, 즉 대소 관계만 중요해야 하며 절대적인 값은 중요하지 않아야 한다.

그러면 좌표 압축을 어떻게 하는지 알아보자. 방법은 간단한데, 가장 작은 값들을 $1$, 그 다음으로 작은 값들을 $2$, 이런 식으로 치환하는 것이다. 상황에 따라서 가장 작은 값들을 $0$으로 치환하는 것도 가능하다. 웬만한 문제에서는 입력되는 수의 개수가 많아야 $10^5 \sim 10^6$ 단위이고 $10^7$개 이상의 수를 입력받는 문제는 거의 없으므로 가장 작은 값을 $1$로 치환했을 때 가장 큰 값은 대부분의 경우 $10^6$ 이하, 아무리 커도 $10^7$보다는 작다고 보면 된다.

간단한 예시를 하나만 확인하고 넘어가자. 다음과 같은 수열이 있을 때

$$[15, 77, 70, 26, 95, 70, 3, 43, 58, 26, 31]$$

여기에 좌표 압축을 적용하면 다음과 같이 된다.

$$[2, 8, 7, 3, 9, 7, 1, 5, 6, 3, 4]$$

같은 값은 같은 값으로 치환되는 점에 유의하자.

구현은 다음과 같다.

#import<bits/stdc++.h>
using namespace std;
struct Value{int i, org, new;} a[100005];
int C(Value a, Value b){return a.org < b.org;}
int D(Value a, Value b){return a.i < b.i;}
int main()
{
    int n;
    for(int i = 1; i <= n; i++)
    {
        a[i].i = i;
        cin >> a[i].org;
    }
    sort(a + 1, a + n + 1, C);
    for(int i = 1; i <= n; i++)
    {
        if(a[i].org > a[i - 1].org)a[i].new = a[i - 1].new + 1;
        else a[i].new = a[i - 1].new;
    }
    sort(a + 1, a + n + 1, D);
}

만약 원래 값인 $org$가 필요 없는 경우 다음과 같은 방법으로 메모리를 아낄 수도 있다.

#import<bits/stdc++.h>
using namespace std;
struct Value{int i, x;} a[100005];
int C(Value a, Value b){return a.x < b.x;}
int D(Value a, Value b){return a.i < b.i;}
int main()
{
    int n, pv, v;
    for(int i = 1; i <= n; i++)
    {
        a[i].i = i;
        cin >> a[i].x;
    }
    sort(a + 1, a + n + 1, C);
    pv = a[1].x - 1;
    for(int i = 1; i <= n; i++)
    {
        v = a[i].x;
        if(a[i].x > pv)a[i].x = a[i - 1].x + 1;
        else a[i].x = a[i - 1].x;
        pv = v;
    }
    sort(a + 1, a + n + 1, D);
}

때때로 $2$차원 좌표에 대해서 좌표 압축을 해야 할 때도 있는데, 그런 경우는 $x$좌표와 $y$좌표를 각각 따로 처리해도 된다. 이것은 차원의 수가 더 많아져도 동일하다.

그러면 이 기법을 어디에 써먹을 수 있는지 알아보자. 좌표 압축을 하면 문제 풀기가 수월해지는 경우에 좌표 압축을 할 텐데, 가장 쉬운 예시는 동적 계획법이다. 주어진 값들에 대해서만 DP 테이블을 채우면 되는 경우 테이블이 너무 크면서 거의 모든 공간이 비어 있는 상황을 피하기 위해 좌표 압축을 사용할 수 있다.

또 다른 예시로 세그먼트 트리가 있다. 집합에 원소가 추가되고 현재의 집합에서 $k$번째로 작은 원소를 찾는 등의 쿼리를 처리해야 할 경우 좌표 압축으로 값의 범위를 줄인 다음 세그먼트 트리를 이용해서 쿼리를 처리할 수 있다.

그밖에도 다양한 유형의 문제에 응용이 가능하지만 앞에서 언급한 두 유형보다 등장하는 빈도가 낮은데다 그것들을 다 설명하면 글이 너무 길어지므로 여기서 언급하지 않는다.

[연습문제]

BOJ 18870. 좌표 압축 (Silver II)

가장 기본적인 좌표 압축 문제이다.

BOJ 18707. Dull Chocolates (Gold III)

좌표 압축 후 누적합을 이용해 답을 구한다.

BOJ 2517. 달리기 (Platinum IV)

좌표 압축 후 세그먼트 트리를 이용해 답을 구한다.