위상 정렬
문제 DAG(Directed Acyclic Graph)는 방항셩이 있는 간선으로 이루어진 그래프 중, 사이클이 없는 그래프를 의미한다. DAG에서는 위상 정렬을 항상 할 수 있다. DAG가 주어질 때, 위상 정렬을 하는 프로그램을 작성하시오. 입력 첫 번째 줄에 그래프의 정점의 개수 V, 간선의 개수 E가 공백으로 분리되어 주어진다. (1 ≤ V ≤ 50,000, 1 ≤ E ≤ 100,000) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보인 x, y가 공백으로 분리되어 주어진다. 이는 x에서 출발하여 y에 도착하는 유항 간선이 존재한다는 것을 의미한다. (1 ≤ x, y ≤ V, x ≠ y) 주어지는 그래프는 항상 DAG이고, 1번으로 들어오는 간선은 없다. 출력 첫 번째 줄에 위상 정렬의 결과를 출..
구간의 대표값
문제 수열 A가 주어졌을 때, 주어지는 구간의 최소값, 최대값, 합을 구하여라. 입력 첫 번째 줄에 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000) 두 번째 줄에 수열의 각 수 Ai가 공백으로 분리되어 주어진다. (1 ≤ Ai ≤ 1,000,000,000) 세 번째 줄에 구간의 수 M이 주어진다. (1 ≤ M ≤ 100,000) 네 번째 줄부터 M개의 줄에 걸쳐 구간의 정보 a, b가 주어진다. 이는 수열의 구간 [a, b]에 대해 최소값, 최대값, 합을 구하라는 의미이다. 출력 각 질의에 대해 최소값, 최대값, 합을 공백으로 분리하여 출력한다. 이 때, 64-bit 정수형의 범위에서 답이 나올 수 있음에 유의하시오. 힌트 입력 예제 5 1 2 3 4 5 3 2 4 3 5 1 4 출력 예제 ..
중앙값
문제 정수가 N개 주어진다. 홀수번째 수가 주어질 때마다, 지금까지 주어진 수의 중앙값을 구하는 프로그램을 작성하여라. 예를 들어 1, 4, 5, 3, 6가 주어진다면, 첫번째 수인 1을 입력받을 때 중앙값이 1이고, 세 번째 수인 5를 입력받을 때까지의 중앙값이 4이고, 다섯번째 수인 6을 입력받을 때까지의 중앙값이 4이므로 1, 4, 4를 순서대로 출력하는 것이다. 입력 첫 번째 줄에 주어지는 정수의 개수 N이 주어진다. (1 ≤ N ≤ 99,999, N은 홀수) 두 번째 줄부터 N개의 줄에 걸쳐 각 줄에 하나씩 정수가 주어진다. (1 ≤ 주어지는 정수 ≤ 1,000,000,000) 출력 홀수번째 수를 입력받을 때마다 그 때까지 입력받은 정수들의 중앙값을 한 줄에 하나씩 출력한다. 힌트 입력 예제 7..
보드 게임
문제 다음 보드 게임은 N장의 카드를 갖고 시작한다.각각의 카드 앞면에는 1번부터 N번까지 번호가 순서대로 적혀 있고, 뒷면에는 빨간색(R), 녹색(G), 파란색(B) 중 하나의 색깔이 칠해져 있다. 항상 1번 마을로부터 시작하여 길이 연결되어 있는 이웃 마을로 이동해 가는데 한 번 이동할 때마다 갖고 있는 카드를 번호 순서대로 한 장씩 내야 한다. 각 길은 빨간색(R), 녹색(G), 파란색(B) 중 하나의 색깔이 칠해져 있는데 만약 내놓은 카드의 색깔과 길의 색깔이 일치하면 10점의 점수를 얻는다. 예를 들어 N이 5이고 1번부터 5번까지의 카드 색깔이 R, G, R, B, G이라고 하자. 지도가 과 같이 주어졌다고 할 때, 1번 마을에서 시작하여 2번 마을로 가면 길의 색깔과 1번 카드의 색깔이 R로..