오늘은 분할 정복 알고리즘의 대표적인 문제 중 하나인 최근접 점의 쌍 찾기에 대해서 알아보겠습니다. 최근접 점의 쌍 찾기 위와 같은 점들이 있다고 합시다. 여기서 가장 가까운 점의 쌍은 어떤 점일까요?? 물론 이 그림에서는 직관적으로 보일 수 있지만, 이러한 점이 많거나 직관적으로 확인하기 어려울 때 말이죠. 우리는 이러한 문제를 알고리즘으로 해결하기 위해서 분할 정복을 사용합니다. 간단한 방법 사실 간단한 방법으로는 모든 점의 쌍에 대한 거리를 구한 후에, 가장 작은 거리를 구하면 됩니다. 하지만 그렇게 되면 시간 복잡도가 O(n^2)이 되어서, 그렇게 좋은 알고리즘 같아 보이진 않습니다. 그래서 우리는 분할 정복을 이용해 시간 복잡도를 낮춰보겠습니다. 분할 정복을 이용한 알고리즘 가장 먼저는 n개의 ..
