boj, 백준) 12781. PIZZA ALVOLOC ( C / C++)
1. 문제 링크 www.acmicpc.net/problem/12781 12781번: PIZZA ALVOLOC 입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다. www.acmicpc.net 2. 문제 개요 볼록 다각형 모양인 피자에서 정점 네 개를 선택하여, 2개의 선분을 만든다. 이 선분이 서로 교차하여 피자가 4조각으로 잘리게 되면 1, 그렇지 않으면 0을 출력하는 프로그램을 작성하자 3. 문제 힌트 선분 교차 알고리즘이다. CCW(외적)을 이용해서 문제를 해결한다. 더 복잡한 2차원 평면에서의 선분교차가 아니고, 볼록 다각형 모서리에서의 정점을 선택하기 때문에 많은 제약이 삭제된다. 종이 ..
boj, 백준) 16933. 벽 부수고 이동하기 3 ( C/C++ )
1. 문제 링크 www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 2. 문제 개요 NxM의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 나는 (1, 1)에서 (N, M)의 위치까지 이동하려고 하는데, 이때 최단 경로로 이동하려 한다. 이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게..
boj, 백준) 15681. 트리와쿼리 ( C/ C++)
1. 문제 링크 www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 2. 문제 개요 간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자. - 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 3. 문제 힌트 정점의 개수가 100,000개. 쿼리의 개수도 100,000개. 쿼리를 입력 받을 때, O(n^2)의 시간으로 처리했다가는 제 시간 안..
boj, 백준) 1637. 날카로운 눈 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/1637 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 2. 문제 개요 정수더미 속에서 날카로운 눈을 이용해 홀수개 존재하는 정수를 찾아야 하는 문제이다. 근데, 정수더미 안에 정수가 적게 있으면 문제가 너무 쉬워지게 된다. 그래서, 정수더미안에 정수를 무지막지하게 많이 넣기로 했다. 정수더미가 주어졌을 때, 그 안에 홀수개 존재하는 정수를 찾는 프로그램을 작성해보자. 3. 문제 힌트 정말 간단하..
boj, 백준) 2166. 다각형의 면적 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 2. 문제 개요 2차원 편명상에 N개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오. 3. 문제 힌트 외적을 사용하자. 두 벡터를 외적한 것은 두 벡터로 만들어지는 평행사변형의 넓이를 나타냄. 4. 문제 풀이 (다른 블로그에서도 좋은 풀이가 있었으나, 중요한 기초 개념인 것 같아 업로드 합니다.) 우선, 다각형은 엄청 찌그러질 수 있기 때문에... 크기를 쪼개고 쪼개서 넓이를 구한 뒤 ..
boj, 백준) 11812. K진 트리 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 2. 문제 개요 각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다. 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가한다. 노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y사의의 거리를 ..