자료구조 및 알고리즘
-
[KOITP] 유령선자료구조 및 알고리즘/문제풀이 2017. 1. 16. 07:59
출 처 : http://koitp.org/problem/SDS_PRO_4_1/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB2193378 (17%)323 문제강희는 정신을 차려보니 낯선 유령선에 납치당해 있었다. 강희는 유령들이 자고 있는 낮 시간에 몰래 유령선에 있는 구명보트를 이용해 탈출하려고 한다. 유령선의 갑판은 동일한 크기의 정사각형 모양 판자가 가로로 W개, 세로로 H개 이어진 모양으로 되어 있다. 강희는 현재 서 있는 위치에서 상하좌우로 움직일 수 있다. 유령선은 매우 낡았기 때문에 강희가 딛고 있는 판자를 벗어나면 판자가 부서지고 만다. 심지어 이미 부서져 있는 판자도 존재한다. 물론 강희는 유령이 아니기 때문에 부서진 판자는 걸어서 지나갈 수 없다...
-
[KOITP] 고속도로 건설자료구조 및 알고리즘/문제풀이 2017. 1. 16. 07:57
출 처 : http://koitp.org/problem/SDS_PRO_10_4/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수2.0 초512 MB724211 (29%)156문제S 왕국의 새로운 정부는 모든 도시를 잇는 고속도로를 건설하려 한다. 그러나 비싼 비용의 문제에 부딪혀, 정부는 최소 비용으로 모든 도시 간을 이동할 수 있게 하고 싶어한다. 또한 하나의 제약이 더 있는데, 언덕 등을 깎지 않는 친환경 건설을 위해 어떤 도시끼리는 직접 도로를 이을 수 없다. 도로 후보의 목록이 주어질 때, 정부를 도와 모든 도시 간을 잇는 고속도로를 건설하는 최소 비용을 알아내자.입력첫 번째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 50,000) 두 번째 줄에 도로 후보의 수 M이 주어진..
-
[KOITP] 위상 정렬자료구조 및 알고리즘/문제풀이 2017. 1. 16. 07:56
출 처 : http://koitp.org/problem/SDS_PRO_10_2/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB852217 (25%)181 문제DAG(Directed Acyclic Graph)는 방항셩이 있는 간선으로 이루어진 그래프 중, 사이클이 없는 그래프를 의미한다. DAG에서는 위상 정렬을 항상 할 수 있다. DAG가 주어질 때, 위상 정렬을 하는 프로그램을 작성하시오.입력첫 번째 줄에 그래프의 정점의 개수 V, 간선의 개수 E가 공백으로 분리되어 주어진다. (1 ≤ V ≤ 50,000, 1 ≤ E ≤ 100,000) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보인 x, y가 공백으로 분리되어 주어진다. 이는 x에서 출발하여 y에 도착하는 ..
-
[KOITP] 그래프 순회자료구조 및 알고리즘/문제풀이 2017. 1. 16. 07:55
출 처 : http://koitp.org/problem/SDS_PRO_10_1/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1474222 (15%)182 문제그래프에서 탐색을 하는 방법에는 여러 가지가 존재한다. 깊이 우선 탐색(DFS; Depth First Search)과 너비 우선 탐색(BFS; Breadth First Search)가 대표적인 탐색 방법이다. 깊이 우선 탐색과 너비 우선 탐색을 하는 프로그램을 작성하시오. 이 문제에서 너비 우선 탐색이란 큐를 사용하여 한 번에 하나의 정점만 탐색을 하는 형태만을 생각한다.입력첫 번째 줄에 그래프의 정점의 개수 V, 간선의 개수 E, 그리고 시작 정점의 번호 S가 공백으로 분리되어 주어진다. (1 ≤ S ≤ V..
-
[KOITP] 세금(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 12. 08:08
출 처 : http://koitp.org/problem/TAX/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.5 초512 MB2545206 (8%)138문제납세의 의무는 국민의 기본적인 의무이다. 세금은 수입에 비례하여 정해진 규칙에 따라 계산되기 때문에, 규칙에 따라서 정확한 수입을 계산하는 것이 중요하다. 여러분은 새로 가게를 열고, 총 N 일 동안 영업을 하였다. 납세의 의무를 성실하게 수행하기 위하여 매 영업일마다 손익(이익 또는 손해)을 기록하여 세무서에 신고하였다. 세금을 매기는데 기준이 되는 수입은 다음 규칙에 의해서 계산된다."1일부터 N일 사이의 어떤 연속된 기간에 대하여 이 기간 동안 손익의 총합을 구한다. 단, 하루 이상의 기간만 고려한다. 다음, 전체 가능한 ..
-
[KOITP] 구간의 대표값(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 12. 08:07
출 처 : http://koitp.org/problem/REPRESENTATIVE/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.5 초512 MB944174 (18%)144문제수열 A가 주어졌을 때, 주어지는 구간의 최소값, 최대값, 합을 구하여라.입력첫 번째 줄에 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)두 번째 줄에 수열의 각 수 Ai가 공백으로 분리되어 주어진다. (1 ≤ Ai ≤ 1,000,000,000)세 번째 줄에 구간의 수 M이 주어진다. (1 ≤ M ≤ 100,000)네 번째 줄부터 M개의 줄에 걸쳐 구간의 정보 a, b가 주어진다. 이는 수열의 구간 [a, b]에 대해 최소값, 최대값, 합을 구하라는 의미이다.출력각 질의에 대해 최소값, 최대값, ..
-
[KOITP] 소수들의 곱셈(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 12. 08:06
출 처 : http://koitp.org/problem/SDS_PRO_3_7/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1686298 (18%)252문제주어지는 K개의 소수만을 인수로 가지는 숫자들 중 1을 제외한 숫자들을 '소수들의 곱셈'이라고 정의하자. 주어지는 소수가 2, 3, 5, 7인 경우 이런, '소수들의 곱셈'에는 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27 등이 있다.K개의 소수가 주어졌을 때 N번째 '소수들의 곱셈'을 알아내는 프로그램을 작성하자.입력첫 번째 줄에 주어지는 소수의 개수 K가 주어진다. (1 ≤ K ≤ 100)두 번째 줄에 N이 주어진다. (1 ≤ N ≤ 1..
-
[KOITP] 구간 합자료구조 및 알고리즘/문제풀이 2017. 1. 12. 08:06
출 처 : http://koitp.org/problem/SDS_PRO_3_5/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.2 초512 MB2250340 (15%)279 문제길이 N의 수열이 주어진다. 이 수열의 초기값은 1, 2, 3, ..., N이다. 그런데 이 수열의 변경이 빈번히 일어나고, 그런 도중에 어떤 연속된 부분의 합을 구하려 한다. 만약 N이 5인 경우를 생각하자. 초기에는 1, 2, 3, 4, 5 가 된다. 이 상황에서 3번째 수를 9로 변경하고 4번째 수를 10으로 변경하면 1, 2, 9, 10, 5가 된다. 이 때, 2번째부터 5번째까지 합을 구하라고 한다면 26을 출력하면 되는 것이다. 또, 이 상태에서 1번째 수를 -5로 변경하고, 3번째 수를 5로 변경하..