인덱스트리, Index Tree - 좌표압축, 리라벨링
좌표압축
- 좌표의 범위가 너무 큰 경우 인덱싱으로 좌표 사이 갭을 없애는 기법
데이터를 정렬해서 다시 순서를 부여하는 것
- 좌표 압축이 필요한 이유
일차원 직선상에 N=10만개의 점이 있고 [x, y] 구간의 점 개수를 출력하는 쿼리가 M개 있을 때, 점의 범위나 x, y의 범위가 [-109, 109] 라면 세그먼트 트리를 구성하려고 했을 때 일반적으로 문제에서 주어지는 메모리 256MB로는 해결이 불가능하다. 하지만 점의 개수에 비해 점의 범위가 훨씬 넓어 sparse 하다는 점을 이용한다면
각 점의 좌표마다 인덱싱을 해, 정렬된 순서로 번호를 매김으로써 답을 구할 수 있다.
백준 18870
문제 : https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net
풀이 : https://st-lab.tistory.com/279
[백준] 18870번 : 좌표 압축 - JAVA [자바]
https://www.acmicpc.net/problem/18870 Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/1887..
st-lab.tistory.com