🔸Coordinate Compression🔸

intro / implementation

 

🔸 넓게 퍼져 있는 값들을 문제 해결을 위해 좌표 압축. (위 그림의 경우 -6~5까지의 퍼져 있는 수들을 차례대로 0 - 1 - 2 - 3 - 4로 나열 가능)

🔸 주의점: 주어진 수들의 크기가 중요치 않고, 크기 순서만이 문제 해결에 필요할 때 좌표 압축 진행

🔸 구현

ex) 랜덤 크기 순으로 나열된 A[1], A[2], A[3], .... A[n]을 좌표 압축

① A[1], A[2], ... , A[n]를 정렬한 새로운 배열 B[] 생성

② 필요 시 중복된 원소들을 제거(중복 카운트 중요치 않을 경우만)

③ 각 A[i]를 B[]에서 이분탐색하여 B[]에서의 A[i] index를 계산

🔸 쉽게 말하자면, 랜덤하게 배치된 다양한 크기의 숫자들을 index의 크기만으로 중복 없이 순서대로 배치해 압축효과를 가져온다. 이 때 hash map으로 각 실제 number(key)에 대응하는 index(value)를 만들 수 있다. (중복 없이 압축이므로 number을 중복 없는 key로 저장)

 

🔸 좌표 압축 상세 과정 (그림)

① 주어진 A 배열

 

② A배열을 정렬 (O(N)) 및 중복 제거(O(N))해서 B 배열 생성

★ 중복 제거법은 내 원소와 내 앞의 원소와 다르다면 B 배열에 넣으면 됨 / 또는 set() 사용

 

③ 생성한 B 배열을 중복없이 압축해 key를 number / value를 index로 저장(hash map 구현 - O(N)) + 또는 binary search를 활용해 각 number의 left index 구하기(O(NlogN))

🔸 이렇게 좌표 압축을 해주어 수의 범위를 확 줄여준다면, 시간과 메모리 성능면 향상

 

🔸  Fenwick Tree나 Segment Tree 활용 가능

 

🔸 좌표 압축은 주어진 수들의 크기 순서만 중요할 때 적용 가능하므로, 그 수들을 index로 사용할 때, 사용하는 메모리를 효과적으로 줄일 때 사용

---

IOI Korea

geeks for geeks