👀 finalfrontier

01) 문제 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 입/출력 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수..

01) 문제 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x1, x2, ..., xM은 x-좌표 값이라고 하자. 각 동물이 사는 위치는 (a1, b1), (a2, b2), ..., (aN, bN)과 같이 x,y-좌표 값으로 표시하자. 동물의 위치를 나타내는 모든 좌표 값은 양의 정수이다. 사냥꾼이 가지고 있는 총의 사정거리가 L이라고 하면, 사냥꾼은 한 사대에서 거리가 L 보다 작거나 같은 위치의 동물들을 잡을 수 있다고 한다. 단, 사대의 위치 xi와 동물의 위치 (aj, bj) 간의 거리는 |xi-aj| + bj로 계산한다. 예를..

01) 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입/출력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표..

01) 문제 2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 있다. 예제 입/출력 4 0 0 10 10 0 10 10 0 # output is 10002) 풀이 평면을 분할한다 분할된 평면에서 최소 거리를 찾는다 서로 분할되어 있는 점들 중에서 최소 거리가 될 수 있는 점들만 탐색하여 최소 거리를 갱신한다. 이전 알고리즘 수업에서 분명히 접했던 문제인데도 바로 구현이 떠오르지 않았다. 위와 같은 흐름으로 divide/combine ..

[1629] 곱셈 1) 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 예제 입/출력 10 11 12 # output is 4 2) 풀이 $\ A^(x+y) = A^x \times A^y$ 임을 이용해 분할 정복으로 풀어야겠다는 생각은 들었는데, 구체적인 구현방법이 떠오르지 않았다. 결국 풀이를 참고했고, 핵심은 모듈러 연산의 성질이라는 점을 알게 되었다. 모듈러 연산의 분배법칙 $(A \pm B), \bmod, C ..

BaekJoon 1007: 벡터 매칭 풀이 방법 집합 P는 n개의 점들의 집합이고, P의 벡터 매칭은 P의 모든 점을 한 번씩 사용하여 만든 벡터의 집합이다. 즉, $P = {(x_1, y_1), (x_2, y_2), \dots , (x_n, y_n)}$ $VM = {(x_i - x_j,\space y_i - y-j)\space|\space 1 \le i, j \le n, i \ne j }$ 따라서 벡터 매칭에 속하는 모든 벡터의 합은 다음과 같이 구할 수 있다. $v_1 = (x_2 - x_1, \space y_2 - y_1)$ $v_2 = (x_4 - x_3, \space y_4 - y_3)$ $ \dots $ $v_{n/2} = (x_n - x_{n-1}, \space y_n - y_{n-1})$ ..

BaekJoon 1005: ACM Craft 풀이 방법 위상 정렬 topological sorting 과 DP를 활용하여 문제를 해결한다. 인접 리스트를 사용해 유향 그래프를 만들고, 진입 간선의 수를 체크하기 위해 degree 배열을 만들어 준다. 정점을 모두 담을 큐도 하나 선언해 준다. from collections import deque time = [0] + list(map(int, input().split())) # time to build result = time.copy() degree = [0] * (N + 1) graph = [[] for _ in range(N+1)] queue = deque([i+1 for i in range(N)]) 먼저, 건물을 짓는 순서 X, Y 가 주어질 때마..