[알고리즘] 분할 정복 - 최근접 점의 쌍 찾기

오늘은 분할 정복 알고리즘의 대표적인 문제 중 하나인 최근접 점의 쌍 찾기에 대해서 알아보겠습니다.

 

 

  최근접 점의 쌍 찾기

 

위와 같은 점들이 있다고 합시다. 여기서 가장 가까운 점의 쌍은 어떤 점일까요??

 

물론 이 그림에서는 직관적으로 보일 수 있지만, 이러한 점이 많거나 직관적으로 확인하기 어려울 때 말이죠.

우리는 이러한 문제를 알고리즘으로 해결하기 위해서 분할 정복을 사용합니다.

 

   간단한 방법

사실 간단한 방법으로는 모든 점의 쌍에 대한 거리를 구한 후에, 가장 작은 거리를 구하면 됩니다. 하지만 그렇게 되면 시간 복잡도가 O(n^2)이 되어서, 그렇게 좋은 알고리즘 같아 보이진 않습니다.

 

그래서 우리는 분할 정복을 이용해 시간 복잡도를 낮춰보겠습니다.

 

 

   분할 정복을 이용한 알고리즘

가장 먼저는 n개의 점을 반절로 나눠줄 것입니다. 아래와 같이 작게 쪼개집니다.

 

이런 식으로 쪼개집니다. 이제 왼쪽과 오른쪽에서 가장 짧은 길이를 찾아봅시다. 

 

좌, 우측 영역에서 가장 짧은 점의 쌍을 알아냈습니다. 그렇다면 이 10개의 점의 쌍 중에서 가장 짧은 점의 쌍이 바로 (4, 5)일까요??

 

아직 모릅니다. 왜냐하면 우리는 가운데 영역을 확인해보지 않았기 때문이죠. 따라서 우리는 아래의 영역에서의 점들의 쌍을 한번 더 고려해볼 필요가 있습니다.

 

 

좌, 우측에서의 가장 짧은 거리가 3이었으므로, 중간 영역도 3만큼 고려해야합니다. 따라서 색칠된 부분에 포함된 점들을 고려해볼 필요가 있습니다.

 

총 3개의 점을 고려해볼 수 있고, 다행히 좌측의 가장 짧았던 부분이 전체 점의 쌍 중에서 가장 작습니다.

 

 

 

우리는 이런 방식으로 최근접 점의 쌍을 찾을 수 있습니다. 이 알고리즘을 우리는 분할정복을 이용한다고 했습니다. 따라서, 위와 완전히 동일한 방식으로 진행되지는 않습니다.

 

이 알고리즘은 쪼갠 구역 내의 점의 개수가 3개 이하일 때까지 분할하여 문제를 해결하고자 합니다. 따라서 바로 위의 그림에서 중간 영역의 점들을 고려하는 것이 아닌 한 번더 쪼개는 과정을 거칠 것입니다.

 

그럼 해당 알고리즘과 완전히 동일한 방법으로 진행해보죠.

 

이런 식으로 쪼개진 부분에서 더 잘게 쪼개야합니다. 좌측 영역을 2개로, 우측 영역도 2개로 쪼개봅시다.

 

 

5개를 좌측 3개와 우측 2개로 쪼갰습니다. 위와 같은 형태가 되었습니다.

 

지금 우리가 다루고 있는 알고리즘은 쪼갠 영역의 점의 개수가 2, 3개일 때 계산하여 작은 점의 쌍을 찾습니다. 따라서, 해당 구역들을 더이상 쪼개지 않고 점의 거리를 구해야합니다.

각 구역에서의 가장 짧은 점을 구했습니다. 이제, 두 구간의 중간 영역을 고려해봅시다.

 

 

 

중간 영역을 고려하여 최근접 점의 쌍을 찾아주었습니다. 이제 분할한 케이스들을 다시 합쳐줍시다.

 

 

자 이 다음에는 또 중간 영역을 고려하여 최소점을 찾아주면 됩니다.

 

 

이렇게 결국 최근접 점의 쌍은 (4, 5)가 되었습니다.

 

   의사코드

/**
 * @param S : x 좌표가 오름차순으로 정렬된 i개의 점의 배열. 
 * @return : 입력된 점들 중에서 최근접 점의 쌍의 거리
 *
 */
closetPair(S){
 if( 점의 개수 <= 3) return 2 또는 3개의 점들 사이의 최근접 쌍
 
 정렬된 S를 S_l과 S_r로 분할함.
 
 CP_l = closetPair(S_l);
 CP_r = closetPair(S_r);
 
 d = min(dist(CP_l), dist(CP_r));
 
 CP_c = 중간 영역에서 좌우의 d만큼의 거리 중 가장 작은 최근접 점의 쌍
 
 return (CP_l, CP_r, CP_c에서 거리가 가장 작은 것)
}

 

 

---

지금까지 분할 정복을 이용하여 최근접 점의 쌍을 찾는 알고리즘을 알아봤습니다. 감사합니다.