좌표 압축
좌표 압축은 어떤 특정 알고리즘이라고 소개하기 보다는 기법이라고 보는게 맞는 것 같다.
정렬을 이용해서 떨어진 좌표의 범위를 줄이는데 쓰이고 세그 트리에서 자주 쓰인다고 한다.
아직 세그트리를 공부하지 않아서 먼저 보인 좌표 압축을 한 번 정리하고 가려고 한다.
백준 18870번 좌표 압축의 예시로 보면 2 4 -10 4 -9를 크기 순으로 2 3 0 3 1로 바꾼다.
방법은 간단한데 우선 index를 달아서 pair로 만들어준다.
1
2
3
2 4 -10 4 -9
-> (2,0) (4,1) (-10,2) (4,3) (-9,4)
다음 앞의 숫자를 기준으로 정렬을 하면
1
(-10,2) (-9,4) (2,0) (4,1) (4,3)
이 된다.
이제 처음의 숫자를 지우고 앞에서부터 0부터 1씩 늘려가며 숫자를 준다.
이 때 같은 숫자라면 같은 숫자를 줘야한다. (rank 주는 것 처럼)
1
(0,2) (1,4) (2,0) (3,1) (3,3)
이제 뒤에 있는 index를 기준으로 맞춰주면 된다.
1
(2,0) (3,1) (0,2) (3,3) (1,4)
다음 index를 지워주면
1
2 3 0 3 1
로 원하는 좌표 압축이 이뤄졌다.
가끔씩 쓰는 테크닉이니 잘 알아두자.