알고리즘 공부방

Andrew's Chain은 주어진 점 집합들의 Convex Hull을 $O(NlogN)$에 구할 수 있게 해주는 Graham's Scan과는 다른 알고리즘이다. Graham's Scan과는 다르게 Upper Hull과 Lower Hull로 분리해낼 수 있다는 장점이 있고, 정렬 또한 각도 정렬이 아닌 단순한 x축 기준 정렬만 필요하다. 1. 전체 점들을 x축 기준, x축이 같다면 y축 기준으로 정렬한다. 2. 스택에 점들을 하나씩 넣으며, 다음 불변식을 유지하도록 삽입한다. 스택의 점들은 시계 방향으로, 즉 ccw가 음수인 방향으로 굽어 있다는 불변식을 만족해야 한다. 불변식을 만족하지 않다면 점들을 위에서부터 삭제하고 현재 점을 삽입한다. 이 과정을 통해 Upper Hull을 구할 수 있다. 3. 배..

Graham's Scan은 주어진 점 집합들의 Convex Hull을 $O(NlogN)$에 구하는 알고리즘이다. 1. Convex Hull에 무조건 포함되는 한 점 S를 잡는다. 일반적으로 x좌표가 최소인 점, 만약 여러개 있다면 y좌표가 최소인 점으로 잡는다. 2. S를 기준으로 전체 점들을 각도 순으로 정렬한다. 만약 S, p, q가 일직선 위에 있다면 S와의 거리 순으로 정렬한다. 3. 정렬한 순서대로 점들을 하나씩 보며, 스택에 점들을 하나씩 추가한다. 단, 스택의 점들은 들어가 있는 순서대로 시계 반대 방향으로, 즉 ccw가 양수로 유지되어야 한다. 이 불변식을 만족할 수 있도록 적절히 스택에서 점들을 제거해준 후, 새로운 점을 추가해준다. #include using namespace std; ..