Divide and Conquer - Closest Pair

Closest Pair

•  두 점 사이의 거리가 최소인 것을 찾자.

---

O(n²) 알고리즘

• 일반적인 방법

두 점 사이의 거리를 모든 점에 대하여 확인.
nC2 만큼의 확인이 필요. = O(n^2)

 

---

O(nlog²n) 알고리즘

• 분할 정복 내에서 Band 가 결정될 때마다 새롭게 Sort 하자!

1. x 좌표에 대하여 sorting → O(nlogn)
(입력은 무작위이기 때문에 sorting 되지 않으면 분할정복 불가)

2. 분할정복 시작 : 재귀의 가장 밑바닥까지 내려간다.
2-1. 왼쪽 최소 dl 오른쪽 최소 dr를 찾고 dl, dr에 대한 최소 d를 찾는다.
2-2. 만약 분할 경계선을 기준으로 둔 두점 사이의 거리가 d 보다 작으면 이 거리가 새로운 d가 되어야 한다.
2-3. 따라서 분할 경계선을 양옆으로 d 만큼의 밴드를 정의한다. 이 밴드 내의 점이어야지만 d보다 작을 수 있다.
2-4. 밴드내의 점들을 y좌표로 sorting 한다. → O(nlogn)

2-5. 각 점들에 대하여 밴드를 벗어나지 않는 2d2d 사이즈의 사각형을 정의한다.
(2d2d 안에는 dd 사각형이 4개가 들어있다.)
이때 dd 사각형 하나당 점은 최대 4개까지 들어있을 수 있다.
초과한다면 d 보다 작은 거리가 분할경계선 외부에서 발생한다.
따라서 2d*2d는 대략 10개 정도의 점이 들어있으므로
밴드 내의 점 하나당 비교해야 될 거리는대략 10개 정도밖에 안 된다.
밴드 내의 모든 점들로부터 점 사이의 거리를 확인한다. → O(n)

2-6. 만약 확인한 점 사이의 거리가 d 보다 작다면 새로운 d가 된다.

3. 확인이 끝나고 d도 결정되었다면 재귀를 벗어나 올라간다.
4. 2-1. 부터 다시 반복한다.
5. 분할정복 끝이 나면 최종적인 d가 답이다.

최종 시간복잡도)
O(nlogn){x sort 1번} + (O(nlogn){y sort} + 2T(n/2){분할 정복} + O(n){밴드 내의 점 확인})
= O(nlogn){x sort 1번} + O(nlog²n){분할 정복}
= O(nlog²n)

---

O(nlogn) 알고리즘

• 분할 정복과 Merge를 같이 하자!

1. x 좌표에 대하여 sorting → O(nlogn)
(입력은 무작위이기 때문에 sorting 되지 않으면 분할정복 불가)

2. 분할정복 시작 : 재귀의 가장 밑바닥까지 내려간다.
2-1. 왼쪽 최소 dl 오른쪽 최소 dr를 찾고 dl, dr에 대한 최소 d를 찾는다.
2-2. 분할 경계선을 기준으로 둔 두 점 사이의 거리가 d 보다 작으면 이 거리가 새로운 d가 되어야 한다.
2-3. 분할 경계선을 양옆으로 d 만큼의 밴드를 정의한다.
이 밴드 내의 점이어야지만 d보다 작을 수 있다.

2-4. 왼쪽 오른쪽 분할된 점들을 y를 기준으로 하나로 Merge 한다.
⇒ y가 sorting 된다. → O(n)

2-5. 각 점들에 대하여 밴드를 벗어나지 않는 2d2d 사이즈의 사각형을 정의한다.
(2d2d 안에는 dd 사각형이 4개가 들어있다.)
이때 dd 사각형 하나당 점은 최대 4개까지 들어있을 수 있다.
초과한다면 d 보다 작은 거리가 분할경계선 외부에서 발생한다.
따라서 2d*2d는 대략 10개 정도의 점이 들어있으므로
밴드 내의 점 하나당 비교해야 될 거리는 대략 10개 정도밖에 안 된다.
밴드 내의 모든 점들로부터 점 사이의 거리를 확인한다. → O(n)

2-6. 만일 확인한 점 사이의 거리가 d 보다 작다면 새로운 d가 된다.

3. 확인이 끝나고 d 도 결정되었다면 이후 재귀를 벗어나 올라간다.
4. 2-1. 부터 반복한다.
5. 분할정복 끝이 나면 최종적인 d가 답이다.

최종 시간복잡도)
O(nlogn){x sort 1번} + (O(n){Merge} + 2T(n/2){분할 정복} + O(n){밴드 내의 점 확인})
= O(nlogn){x sort 1번} + O(nlogn){분할 정복}
= O(nlogn)