💡최근접 점의 쌍 (Closest Pair) 문제? 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 💡간단한 해결 방법 : O(n^2) 알고리즘 모든 점에 대해 각각의 두점 사이의 거리를 계산하여 가장 가까운 점의 쌍 찾기 비교헤야 할 쌍은 몇개? nC2 = n(n-1)/2 = O(n^2) 한쌍의 거리 계산은 O(1) 따라서 시간 복잡도는 O(n^2) 💡보다 효율적인 해결방법 : 분할 정복 이용 n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍 찾기 2개의 부분해 중에서 짧은 거리 (d)를 가진 점의 쌍을 일단 찾기 (재귀적으로) 결합 : 두개의 부분해를 취합할 때는 반드시 두 부분 문제서 각각 한 점 씩 포함되는 점의 쌍 중에서 그 거리가..
