[알고리즘] Closet Pair of Points (최근접 점쌍 문제)

Closet Pair of Points (최근접 점쌍 문제)

포스트 난이도: HOO_Middle

---

# Closet Pair of Points

Closet pair of points는 평면에서 points들 간의 Euclidean distance에 대한 가장 작은 값을 구하는 알고리즘이다. Closet pair of points이라고 하면 한국에서는 최근접 점쌍 또는 최근접 점쌍 문제라고 부른다. 또한 여기서 말하는 Euclidean distance는 유클리드 거리, 보다 더 쉬운 예제를 들자면 점과 점 사이의 거리를 구하는 공식을 의미한다. 더 쉽게 말하자면, 수학에서 함수 부분에서 배우는 점과 점 사이의 거리를 구하는 공식이나, 삼각형을 통한 기울기를 구하는 공식을 생각하면 이해하기 쉽다. Closet pair of points에 대한 기본적인 개념은 알고 있다고 가정하고 Closet pair of points에 대한 원리를 살펴보도록 하겠다. 일단 간략하게 Closet pair of points를 구하는 방법은 아래와 같은 순서대로 진행된다.

---

# Closet pair of points 알고리즘 순서

1. 평면에 있는 points (필자는 여기서 노드라고 부르겠다.)를 절반으로 나눈다.
2. 나눠진 구분선을 기준으로 왼쪽과 오른쪽에 노드간 짧은 거리를 찾는다.
3. 왼쪽과 오른쪽 짧은 노드 간 거리를 min(dL, dR)이라고 정의한다.
4. 중앙 구분 선을 기준으로 제일 짧은 값(dL이 dR보다 짧을 경우 dL이 기준이 된다.)을 기준으로 양 옆에 1/2 dL 길이만큼의 추가적인 구분 선을 그려준다.
5. 구분 선 안에 포함된 노드들 간의 거리를 확인하여 기존의 짧은 거리 값보다 더 짧은 값이 있는지 확인한다.

---

# Closet pair of points 알고리즘 원리

위에 작성된 요약한 5가지 내용으로는 Closet pair of points를 이해하기가 쉽지 않다. 하지만 포기하지말고 아래의 원리 예제 그림을 찬찬히 살펴보면 훨씬 더 이해하기 수월할 것이다.

예를 들어, 위와 같이 총 8개의 SMILE PEOPLE 있다고 가정해 보자. 이 사람들은 거리가 최대로 가까운 사람 간의 거리와 그게 누구인지를 알고 싶어 한다. 물론 눈으로 확인하면 금세 어떤 사람(노드) 간의 거리가 가까운지 바로 알 수 있다.

글쓴이가 간단하게 예제를 들기 위해 8개의 사람 즉 노드들만을 이용했지만 노드의 수가 무수히 많아지게 된다면 일일이 눈으로 확인하기는 어렵다. 이때 사용되는 방식이 바로 CLOSET PAIR OF POINTS이다. CLOSET PAIR OF POINTS에서 보여주고자 하는 내용은 MERGING과 RECURSIVE RETURN이라는 점을 생각하면서 아래의 예제를 살펴보도록 하자.

우선은 절반의 노드 위치에 임의의 선을 그려준다. 여기서는 8개이기 때문에 4개씩 나누어지는 걸 알 수 있다.

임의의 선을 기준으로 왼쪽과 오른쪽의 노드 간 최단 거리를 찾는다. 해당 예제에서는 왼쪽의 거리가 오른쪽의 최단 거리보다 짧다는 걸 알 수 있다.

 

문제는 바로 임의의 선이 그어진 쪽에 더 짧은 거리가 존재할 수 있다는 것이다. 위의 예제에서도 필자가 일부러 중심에 더 짧은 예제를 넣어 두었다. 절반으로 나눔과 동시에 TIME COMPLEXITY를 줄일 수 있었지만 이렇게 예외의 케이스가 발생할 수 있다. 따라서 이러한 예외의 케이스를 처리할 수 있도록 해주어야 하는데 그게 바로 우리가 줄곧 이야기해 온 CLOSET PAIR OF POINTS인 것이다.

 

CLOSET PAIR OF POINTS라는 의미답게 최단거리, 즉 여기서는 L값을 기준으로 양 옆에 새로운 임의의 선을 그려준다. CLOSET PAIR OF POINTS의 주된 목적은 알고리즘의 효율성 증대이다. 따라서 절반으로 나눠서 비교하고 가운데 임의의 선 기준으로 노드 간의 거리가 우리가 구한 왼쪽 또는 오른쪽의 최단 거리보다 더 짧은지만 확인해 주면 된다. 한마디로 CLOSET PAIR OF POINTS를 사용하지 않을 경우 하나하나 노드 간의 거리를 확인해왔던 거와 달리 더 짧은 시간에 MERGING과 RECURSIVE RETUREN 방식으로 원하는 결과를 산출해 낼 수 있다. 따라서 O(n log n) TIME COMPLEXITY가 되면서 효율성이 증대된다.

---

# In conclusion, 3줄 요약

1. MERGING TWO PRE-SORTED LISTS

2. MERGING AND RECURSIVE RETURN

3. O(n log n)

---