Andrew's Algorithm (1) 썸네일형 리스트형 99. Andrew's Algorithm 앤드류 알고리즘(Andrew's Algorithm)은 점 $n$개의 볼록 껍질을 $\Theta(n\text{ lg }n)$ 시간에 찾는 또다른 알고리즘으로, 앞에서 소개한 그레이엄의 스캔보다 구현이 간단한 편이다. 모노톤 체인(Monotone Chain)이라는 이름으로도 알려져 있다. 이 알고리즘은 점들을 정렬하는 기준을 각도 대신 좌표로 하며, 위쪽 껍질과 아래쪽 껍질을 따로 구하게 된다. 구체적인 작동 방법은 다음과 같다. 1. 점들을 $x$좌표가 증가하는 순서대로, $x$좌표가 같다면 $y$좌표가 증가하는 순서대로 정렬한다. 2. 점을 앞쪽부터 차례로 확인하면서 그레이엄의 스캔과 같은 방식으로 볼록 껍질을 찾는다. 마지막 점까지 확인하면 볼록 껍질의 윗부분이 완성된다. 3. 점을 뒤쪽부터 차례로 확.. 이전 1 다음
