hye0.log hye0.log

최근접 점쌍 찾기

• [알고리즘] 최근접 점쌍 찾기

  Computer Science/Algorithm 2021. 12. 16. 03:06

  최근접 점쌍 찾기 2차원 평면상에 있는 N개의 점들 중에서 서로의 거리가 가장 가까운 두 점을 찾는 문제 간단한 방법 모든 상의 거리를 모두 계산하여 가장 가까운 쌍을 찾는 것 시간 복잡도 O(N^2) 정렬을 사용한 방법 합병 정렬 알고리즘에서 사용하는 분할-정복 기법을 사용 시간 복잡도 O(N log N) 분할-정복 기법을 사용한 최근접 점쌍 찾기 알고리즘 X 좌표 값을 사용해 점을 정렬한 다음 반으로 나눔 가장 가까운 쌍을 이루는 두 점은 모두 한쪽 절반에 있든지 아니면 하나는 한쪽 절반에, 다른 하나는 나머지 절반에 있음 가장 가까운 쌍을 이루는 두 점이 분할선(dividing line)을 가로지르는 경우 효과적으로 검사할 수 있는 방법이 필요 알고리즘 동작 과정 동작 과정을 표로 나타 낼 수도 있..

  Read More