최근접 점의 쌍 찾기 (Closest Pair of Points Problem) 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 간단한 idea 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾는다 example 1, 2, 3, 4, 5 총 5개의 점이 주어진 경우 비교해야 할 쌍의 개수 = nC2 = n(n-1)/2 시간 복잡도는 O(n^2) O(n^2)보다 효율적인 분할 정복 이용 n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 찾는다 2개의 부분해를 취합할 때 아래와 같이 양쪽을 비교해서 짧은 해라고 답으로 정할 수 없다. 거리가 짧은 해 이내..
