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축의 양의 방향이 이루는 각도가 작은 것에서 큰 순으로 번호를 ..
1. 문제 11371번: The Big Eye in the Sky (acmicpc.net) 11371번: The Big Eye in the Sky For each test case, output to a newline the number of degrees (rounded to the closest integer) to rotate the Eye. Note that each test case is rotating from the x-axis, not from the previous orientation of the Eye. www.acmicpc.net 1사분면 위의 (x,y)가 (0,0)과 양의 x축과 이루는 각도를 구하는 문제 2. 풀이 다음 그림과 같이 (a,b)에 대하여 arctan(b/a)를 구하..
1. 픽의 정리(pick's theorem) 좌표가 모두 정수인 점을 격자점(lattice)이라고 부른다. 2차원 좌표평면에서 모든 꼭짓점이 격자점인 다각형이 자기 자신이 교차하지 않을때(not self-interaction), 넓이가 A이고 내부에 있는 격자점의 개수가 I이며 둘레(변)에 있는 격자점의 개수가 B이면... $$A = I + \frac{B}{2} - 1$$이 성립한다. 여러 경우의 수로 나눠서 증명하는데, 조금 까다롭다... 읽어보는걸로 만족하고 생략 https://www.youtube.com/watch?v=GTeZd_IdcoY 영상이 설명을 잘해주고 있는데... 주어진 다각형을 내부의 격자점 수가 0개이고 경계선 위 격자점의 개수가 3개인 삼각형으로 도형을 모두 분할할 수 있고, 이 삼..
1. 문제 18044번: Polygon (acmicpc.net) 18044번: Polygon You are given n segments of lengths ℓ1, ℓ2, . . . , ℓn, respectively. Determine the largest possible circumference of a convex polygon that can be constructed using these segments (in any order, and not neccessarily all of them). The polygon must be www.acmicpc.net 2. 풀이 convex polygon은 앞으로 배울것 같지만... 지금은 모든 내각이 180도보다 작거나 같은 도형이라고 이해하면 될 것 같다 ..
1. 문제 16931번: 겉넓이 구하기 (acmicpc.net) 16931번: 겉넓이 구하기 크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다. 종이의 각 칸에 놓인 정육면체의 개수가 주어 www.acmicpc.net 2. 풀이 위,아래, 앞,뒤,왼쪽,오른쪽에서 보이는 면의 개수를 전부 더하면 될 것이며 면의 개수는 어떻게 구하지? n*m 크기의 바닥 아래에 정육면체를 쌓았을때, 위나 아래에서 봤을때는? 당연히 n*m개씩 보일 것이다. 왼쪽과 오른쪽에서 봤을때는? 위 그림이 1 3 4 2 2 3 1 2 4 와 같이 주어지는데, 왼쪽에서 본다면, 1 3 4 >>>>>> 2 2 3 1 2 4 처럼 상상해본..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
