1. 문제 10903번: Wall construction (acmicpc.net) 10903번: Wall construction 첫 번째 줄에는 두 개의 자연수 N, R (1 ≤ R ≤ 100)이 공백으로 구분되어 주어진다. N은 기둥의 개수이며, R은 기둥의 반지름으로 모든 기둥은 같은 반지름을 가진다. 이후 N개의 줄에는 미술관의 www.acmicpc.net 2. 풀이 convex hull의 둘레의 길이를 구해야하는데.. 단순히 둘레의 길이만 구한다면.. convex hull의 모든 꼭짓점을 찾고 꼭짓점끼리 거리를 합하면 그만이지만 이 문제는 꼭짓점이 둥근 형태라는게 문제다. convex hull의 꼭짓점을 찾고 꼭짓점끼리 거리를 구한다음, 파란색으로 동그라미 된 둥근 부분의 길이도 구해야한다 이를 ..
1. 선분 교차 기본형 두 선분 (A,B)와 (C,D)가 주어질때 두 선분이 교차하는가? 교차하지 않는가? 직선의 방정식 구해서.. 교점을 구해보고.. 기울기 비교해보는 등 여러 방법을 사용해볼 수 있지만.. 가장 일반적인 방법은 CCW를 이용하는 것이다. https://deepdata.tistory.com/955 기하학의 사칙연산인 CCW(Counter-ClockWise) 알고리즘 배우기 https://rebro.kr/10 CCW (Counter-ClockWise) - (1) CCW (Counter-ClockWise) - (1) CCW 알고리즘은 수 계산에서의 사칙연산처럼, '기하 알고리즘'에서 가장 기본적인 알고리즘이다. 즉, 기하 알고리즘에서 매우 자주 이 deepdata.tistory.com 다음..
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개인 삼각형으로 도형을 모두 분할할 수 있고, 이 삼..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
