중독에 취약 중독에 취약

1. 개요 자비스의 행진 알고리즘은, convex hull 문제를 해결하기 위한 알고리즘이다. 말만 들으면 아이언맨에 나온 자비스가 생각난다. Jarvis라는 사람이 만들었고 마치 행진하듯 알고리즘이 진행되어 Jarvis's March라는 이름이 붙었다. 또 다른 이름으로는 선물 포장 알고리즘이라는 이름이 있다. 이 알고리즘은 다른 알고리즘들에 비해 상당히 속도가 느리다는 단점이 있지만, 3차원 이상의 공간으로 확장될 수 있다는 장점이 있다. 2. 알고리즘 간단하게 진행하기 위해, 3개의 정점들이 같은 직선 위에 있는 경우는 없다고 가정한다. 처음 시작할 때, 시작점 $P_0$에서 시작하고 $i = 0$으로 설정한다. 이때, $P_0$는 Convex hull에 포함되어 있는 점 중 하나로 일반적으로 가장..

1. 개요 convex hul에 속한 모든 정점들을 찾는 알고리즘으로, $O(n\log{n})$시간의 시간 복잡도를 가진다. 효과적으로 이전 값을 탐색하고 삭제하기 위해 stack 구조를 활용하여 알고리즘이 진행된다. 3차원 공간에서는 결과를 얻을 수 없다..는 단점이 있다. 컴퓨터에서는 floating point로 각도를 계산해야 하니... 오차가 꽤나 많이 생긴다는 단점도 있다. 2. 알고리즘 가장 작은 y좌표값을 갖는 정점을 시작점 $P$로 잡는다. 만약 같은 y좌표를 갖는 정점이 여러개라면 x 값이 가장 작은 것을 선택한다. 정점 목록을 $P$와 x축이 이루는 각도에 따라 정렬한다. 직접 각도를 계산할 필요는 없다. x축과 이루는 각이므로, 직선의 기울기, 내적으로도 쉽게 판별이 가능하다. 만약 ..