최근접점찾기(Closest Pair) - 분할정복

최근접 점 찾기 알고리즘이란, 가장 가까운 두점을 찾는 알고리즘이다. 

가장 가까운 두점을 찾는 방식에 대해서 고민해보자.

방법 1: 모든 경우의 수를 계산 => 무식하지만 확실한 방법 (Brute-Force)

But, 점 개수가 몇개 없으면 괜찮지만, 점의 개수가 많아지면 비효율적이다. 

 

1-1) 왜 비효율적인가?

모든 경우를 계산한다고 하면 n개중에서 2개를 뽑아내는 경우의 수(수학에서 조합의 이다)

IF) n=5개 일때(=점이 총 5개일 때) : 10번
     n=1,000개 일때 : 499,500 번(약 50만번)

     n= 10,000개 일때 : 49,995,000 번(약 5,000만 번)

=> 점(n)이10배 늘어났는데, 비교 횟수는 100배로 증가..😵‍💫

 

이때의 시간복잡도 O(n2)

 

방법2: 그래서 빠르게 풀려면, '분할 정복(Divide and Conquer)'이 필요합니다. 

*분할정복 : 잘게 쪼개서 해결하고 합치는 전략

 

0. 준비 작업 (사전 정렬) 

- 데이터가 정렬되어 있고, 정렬되어 있지 않고에 따라서 시간 복잡도의 결과가 달라집니다. 

- 정렬이 되어 있다고 가정하고 진행합니다. 

- 정렬은 Px, Py로 각각 x좌표, y좌표를 기준으로 정렬합니다. (정렬은 성능을 일정하게 보장하는 합병 정렬을 주로 사용한다고 가정하겠습니다)

 

1. 분할 (Divide) 쪼개기

- 모든 점을 x좌표 기준으로 정렬한 다음, 정확히 반으로 나눠서 왼쪽그룹과 오른쪽 그룹으로 만듭니다. 

 

2. 정복 (Conquer) 각자 해결하기

• 왼쪽 그룹에서 가장 가까운 두 점을 찾는다. (이 거리를 d_left 라고 하자)
• 오른쪽 그룹에서 가장 가까운 두 점을 찾는다. (이 거리를 d_right 라고 하자)

여기에서 제일 짧은 거리를 임시 정답 d로 정한다. 

 

3. 놓친케이스 : 왼쪽그룹에 속해있으면서 오른쪽으로 그룹에 있는데 거리가 짧은 케이스

• 중간 영역(Strip) 만들기: 왼쪽과 오른쪽 그룹을 나눴던 중간선(L)을 기준으로, 양쪽으로 거리 d만큼 떨어진 좁은 영역을 만든다. 왜냐하면, d보다 더 가까운 점이 있다면 반드시 이 영역 안에 존재할 수밖에 없기 때문
• 영역 안에서만 비교하기: 이제 이 좁은 영역 안에 들어온 점들만 비교한다. 이때도 모든 점을 비교하는 것이 아니라, 각 점 주변의 몇 개 점하고만 비교하면 된다

 

4. 시간복잡도

1) 총 층 : log2(n)임으로, log n이다. 

2) 각층에서 하는 일 : 각 층의 데이터 총량은 그대로 n이다. 그리고 n개의 데이터를 정렬하는 효율적인 시간 복잡도는 nlog n이다. 

3) 최종 시간 복잡도 = (총 층의 개수) × (한 층에서 하는 일) = log n * n log n = O(n(log n)^2 )

 

 

---

Reference

인하대학교 소프트웨어융합공학과 알고리즘 수업