1. 모노톤 체인(monotone chain) 볼록 껍질(convex hull)을 구하는 두번째 알고리즘 graham scan과는 다르게 점을 정렬하는 방법이 다르고, 아래쪽 껍질과 위쪽 껍질을 구하여 둘을 합치는 방식으로 구한다 구체적으로는... 1) 주어진 점을 x좌표 순으로 오름차순 정렬하고 x좌표가 같으면 y좌표를 기준으로 오름차순 정렬 2) 첫번째 점과 두번째 점을 스택에 넣는다. 3) 이제 순서대로 세번째 점부터 순회하면서 조건에 맞으면 스택에 차례대로 집어 넣는다. 3-1) 스택의 -2번, -1번 점과 새로 추가하려는 점이 CW를 이루면 스택에 집어 넣는다. 3-2) CW를 이루지 않는다면 CW가 될 때까지 스택의 마지막 점을 pop한다 4) 마지막에 스택에 남아있는 점들이 볼록 껍질의 윗 ..
1. 볼록 껍질(convex hull) 주어진 모든 점을 포함하는 최소 크기의 볼록 집합 여기서 볼록 집합(convex)이라는 것은 집합 내에 임의의 두 점을 잡아 선분을 그릴때, 해당 선분이 집합 내에 포함되는 집합이다. 아래 그림에서 왼쪽은 볼록 집합이지만 오른쪽은 볼록 집합이 아니다. 직관적으로는 무한한 크기의 고무줄(검은색)을 주어진 모든 점을 둘러싸도록 크게 당긴 다음, 손을 놓았을때 점에 탁 걸리면서 만들어지는 도형(파란색) 2. 그라함 스캔(graham scan) 볼록 껍질을 구하는 대표적인 알고리즘 중 하나 1) 주어진 점을 각도 순으로 정렬 점을 각도 순으로 정렬한다는 말은... 기준점을 잡고 기준점과 점들을 연결한 선분과 x축의 양의 방향이 이루는 각도가 작은 것에서 큰 순으로 번호를 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
