해나의 컴공생존기

Convex Hull 이란 평면 좌표에서 어떤 점들이 있을 때 모든 점들을 포함 하는 가장 작은 볼록 다각형을 의미한다. (점들의 바깥에서 고무줄을 놨을 때 만들어지는 도형) 점들을 정렬하는 과정이 필요하기 때문에 Convex Hull 을 만드는 알고리즘의 시간 복잡도는 O(nlog n)보다 빠를 수 없다. 1. Count - Clock - Wise (CCW) 이 알고리즘은 세 점이 관계를 표현할 때 유용하다. A(x1,y1), B(x2,y2), C(x3,y3)가 있다고 해보자. A와 B의 기울기 + B와 C의 기울기를 가지고 회전 방향을 알 수 있다. A와 B의 기울기 > B와 C의 기울기 → 우회전 A와 B의 기울기 < B와 C의 기울기 → 좌회전 A와 B의 기울기 = B와 C의 기울기 → 한 직선 ..

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만큼의 거리에 선을 그으면 위 ..