좌표압축
- 좌표의 범위가 너무 큰 경우 인덱싱으로 좌표 사이 갭을 없애는 기법
데이터를 정렬해서 다시 순서를 부여하는 것
- 좌표 압축이 필요한 이유
일차원 직선상에 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
'IT Tech > Application' 카테고리의 다른 글
| ELK 스택 (Elastic Search) (0) | 2023.11.06 |
|---|---|
| SAST ( Static Application Security Testing) (0) | 2022.11.09 |
| 벨만포드 알고리즘 (0) | 2022.09.17 |
| 트리 : 우선순위 큐 (1) | 2022.09.16 |
| 트리 : MST (Minimum Spanning Tree), 최소신장트리 (2) | 2022.09.16 |
