Problems by Brute Force

◎ Closest-Pair Problems

• Closest-Pair Problems

  • 2차원 평면 상의 n개의 점이 입력으로 주어딜 때, 거리가 가장 가까운 한쌍의 점을 찾는 문제

• 기본 해결 방법

  • 모든 두 점사이의 거리를 계산하여 모두 비교
  • $nC_2 = n(n-1)/2 = O(n^2)$ 의 시간복잡도를 가짐 (꽤 오래걸림)

• 시간복잡도를 고려한 해결방법
  

// if (점이 3개 이하) return 모든 경우 고려한 최솟값

// 세가지 구역으로 분리
// 1. x값만 고려했을 때, 중간값 이전 구역
// 2. x값만 고려했을 때, 중간값 이후 구역
// 3. 경계 지점에서 1,2 에서 구한 최솟값의 양 옆 구역에서 최솟값 구함

// return 1,2,3 에서 구한 곳에서의 최솟값
// [재귀 이용]

• 참고 블로그 : https://dudri63.github.io/2019/01/19/algo8/

◎ 관련 문제

• Convex-Hull Problems : 볼록 껍질 알고리즘
  • https://ko.wikipedia.org/wiki/%EB%B3%BC%EB%A1%9D_%EA%BB%8D%EC%A7%88_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98