가장 가까운 두 점

def closest_pair(points):
    def sq_dist(p1, p2):
        return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

    def closest_band(mid_band, d):
        min_d = d
        mid_band.sort(key=lambda x: x[1]) # y좌표정렬

        for i in range(len(mid_band)):
            for j in range(i+1, len(mid_band)):
                if (mid_band[j][1] - mid_band[i][1])**2 < min_d:
                    dist = sq_dist(mid_band[i], mid_band[j])
                    if dist < min_d:
                        min_d = dist
                else:
                    break
        return min_d

    def closest_pair_rec(pts):
        if len(pts) <= 3:
            return min(sq_dist(pts[i], pts[j]) for i in range(len(pts)) for j in range(i+1, len(pts)))

        mid = len(pts) // 2
        left_pts = pts[:mid]
        right_pts = pts[mid:]

        left_min = closest_pair_rec(left_pts)
        right_min = closest_pair_rec(right_pts)

        d = min(left_min, right_min)

        mid_x = left_pts[-1][0]
        mid_band = [p for p in pts if abs(p[0] - mid_x) < d]

        return min(d, closest_band(mid_band, d))

    points.sort(key=lambda x: x[0]) # x좌표정렬
    return closest_pair_rec(points)

n=int(input())
points=[]
for _ in range(n):
    points.append(tuple(map(int,input().split())))
print(closest_pair(points))

이 코드는 가장 가까운 두 점을 찾는 문제를 해결하기 위한 파이썬 코드입니다. 이 문제는 컴퓨터 과학과 수학에서 자주 등장하는 문제 중 하나로, 주어진 점들 중에서 가장 거리가 짧은 두 점의 쌍을 찾는 것입니다. 이 코드는 분할 정복(divide and conquer) 방법을 사용하여 문제를 해결합니다. 분할 정복 방법은 큰 문제를 작은 문제로 나누어 해결한 다음, 그 해결책을 합쳐서 전체 문제의 해결책을 얻는 알고리즘 설계 패러다임입니다.

1. 알고리즘 설명

이 코드는 크게 세 부분으로 나눌 수 있습니다: sq_dist, closest_band, 그리고 closest_pair_rec.

1.1 sq_dist(p1, p2)

• 이 함수는 두 점 p1과 p2 사이의 거리의 제곱을 계산합니다. 거리의 제곱은 두 점 사이의 실제 거리를 비교하는 데 필요한 모든 정보를 제공하며, 제곱근을 계산하는 것보다 계산적으로 효율적입니다.

1.2 closest_band(mid_band, d)

• 이 함수는 중간 영역에 있는 점들을 대상으로 하여, 주어진 거리 d보다 작은 거리를 가진 가장 가까운 점의 쌍을 찾습니다. 이 함수는 y 좌표에 따라 점들을 정렬하고, 각 점에 대해 y 좌표의 차이가 d보다 작은 점들만을 대상으로 거리를 계산합니다. 이는 검사해야 하는 점의 수를 크게 줄여줍니다.

1.3 closest_pair_rec(pts)

• 이 함수는 분할 정복 기법의 핵심입니다. 주어진 점들을 x 좌표에 따라 정렬한 후, 리스트를 두 부분으로 나눕니다. 각 부분에 대해 재귀적으로 함수를 호출하여 가장 가까운 점의 쌍의 거리를 찾습니다. 그 후, 중간 영역에서 가장 가까운 점의 쌍을 찾기 위해 closest_band 함수를 호출합니다. 최종적으로, 세 부분 중 가장 짧은 거리를 반환합니다.

2. 전체 프로세스

전체 프로세스는 사용자로부터 점의 개수 n과 각 점의 좌표를 입력받아, closest_pair 함수를 호출하여 가장 가까운 두 점 사이의 거리의 제곱을 출력합니다. closest_pair 함수는 먼저 점들을 x 좌표에 따라 정렬하고, closest_pair_rec 함수를 호출하여 문제를 해결합니다.

3. 효율성

이 알고리즘은 분할 정복 방법을 사용함으로써, 모든 점의 쌍을 직접 비교하는 방법보다 훨씬 효율적입니다. 전체 점의 수가 n일 때, 이 알고리즘의 시간 복잡도는 대략 O(n log n)입니다. 이는 점들을 정렬하는 데 걸리는 시간과, 각 단계에서 중간 영역의 점들을 처리하는 데 필요한 시간에 기인합니다.

 

https://youtu.be/Iv-KOgzQ-G8