알고리즘 정리
Closest Pair 최근접 점쌍 (2261 가장 가까운 두 점 )
공부절대안함
2020. 11. 12. 20:37
http://acmicpc.net/problem/2261
2261번: 가장 가까운 두 점
첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있
www.acmicpc.net
1.접근
n이 100000이므로 O(N^2)으로는 풀 수 없다. 내가 아는 방법이 없는 것 같아서 구글링으로
라인 스위핑 알고리즘과 분할정복을 통한 closest pair 방법이 있었는데 라인 스위핑이 아직 어려워서 분할정복으로 풀어보았다.
라인스위핑:www.acmicpc.net/blog/view/25
closet pair:casterian.net/archives/92
2.풀이
모든 부분을 분할해서 l,r,c 3가지 모든 부분을 구하는 것이다.
모든점의 거리의 최소값은 이 사이에 있을 수 밖에 없다.
우선 좌표값들을 x에 대해서 정렬시키고 mid좌표값으로 분할선을 잡아서 거리를 구하기 쉬운 2개씩 나눠질때까지 분할정복을 한다. 그에 따라서 최소값 d가 구해질 때마다 분할선 근처 값들만 찾아서 새로운 리스트를 만들고 그 리스트를 y에 대해 정렬한 후 d값을 갱신해 가면서 밑으로 올려서 쓸어 담는 식으로 최소값을 구한다.
3.코드
4.배운점
- closet pair은 O(nlog^2n)의 시간복잡도를 가진다.
- y값에 대해서 정렬했을 때 n^2이라고 생각할 뻔 했지만 y좌표도 최소값 사이의 값만 보면 된다.
- 라인스위핑은 나중에 더 공부해야겠다 set에서 이해가 잘 안 되었다.