1. Closest pair Closest pair은 주어진 점들 중에서 가장 가까운 쌍을 찾는 문제이다. 이 문제는 직관과 심하게 충돌하는 경우가 많다 1차원일 때는 단순하게 sorting 하면 구할 수 있고 2차원일 경우 두 점사이의 거리공식으로 구할 수 있다. 하지만 이 경우에는 O(n^2) 이 필요하다. 이 방법은 어렵지 않다. 우리의 목표는 O(nlogn)이다. 2. Divide and Conquer 먼저 이들을 절반으로 나눈다. (나누는 것은 x 를 기준으로 sorting 한 뒤 나눠주면 된다) 나눠거 각각 가장 최소거리를 구해준다. 왼쪽의 최소걸이는 DL 오른쪽의 최소거리를 DR이라고 하자. D = min(DL , DR) 라고 D를 정의하자. 중심 선으로부터 D만큼의 거리에 선을 그으면 위 ..
