알고리즘 5주차 - 최근접 점의 쌍 찾기 알고리즘

최근접 점의 쌍 문제 (Closest Pair) 문제 

• 개념 : 2차원 평면 상 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제
• 방법 :
  • 모든 점 대해 두 점 사이 거리 계산 후 비교 => 시간복잡도 O(n^2)
  • 분할 정복 => 점 반으로 나눠 짧은 거리 점 각각 구함 => 반으로 나눈 경계면에 가장 가까운 점끼리 길이 구함
• 시간복잡도 : 각 층 O(nlog) * 층 수 O(logn) = O(nlog^2n)
• 특징 : 
  • 분할 정복 부적절 경우 : 분할될 때마다 부분문제의 입력 크기 합이 더 커지는 경우 (n 번째의 피보나치 수를 구하기)
  • 취합 과정 주의해야
  • 입력을 분할만 한다고 해서 효율적인 알고리즘이 되는 건 아님
  • 기하 관련 문제들이 효율적인 분할 정복 알고리즘으로 해결됨

<코드>