최근접점 (1) 썸네일형 리스트형 [알고리즘 공부] 최근접 점의 쌍 찾기 알고리즘(Closest Pair of Points) - python 파이썬 ▶ 최근점 점의 쌍을 찾는 문제? 최근접 점의 쌍(Closest Pair)을 찾는 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제입니다. 바로 그 문제를 해결하기 위한 방법은 효율적인 분할 정복을 이용하는 것입니다. n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 쌍을 찾고, 2개의 부분 해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾습니다. 여기서 주의할 점! 취합할 때 중간 영역을 고려해야합니다. 이게 무슨 말이냐면, 분할된 왼쪽 점 중에 하나, 오른쪽 점 중에 하나가 최근접점 쌍이 될 수 있습니다. 그래서 중간 영역도 왼쪽 부분과 오른쪽 부분의 최단 거리인 10과 15중에 더 짧은 거리 10이내에 있는 각각 왼쪽과 오른쪽 점들만 거리 .. 이전 1 다음
