자료구조 및 알고리즘/문제풀이
-
[KOITP] 웜홀(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 17. 08:09
출 처 : http://koitp.org/problem/SDS_PRO_4_6/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수2.0 초512 MB2087350 (17%)259문제그의 많은 농장들을 탐험하던중, 존은 몇 개의 놀라운 웜홀을 발견했다. 웜홀은 현재 농장에서 다른 농장으로의 이상한 단방향 통로로써 당신이 들어갔던 시간보다 이전시간으로 시간을 되돌린다. 존의 농장은 N개의 농장과 M개의 양방향 도로, W개의 웜홀로 구성되어있다. 그리고 각 농장은 편의상 농장1, 농장2, … ,농장 N이라고 이름붙여주자.존은 갑자기 현재위치에서 출발해서 여행을 하다 다시 현재위치로 돌아왔을 때 시간이 되돌아 가 있는 경우가 있는지 궁금해졌다. 존을 도와 시간을 되돌리는 여행이 가능한지 구하는 프..
-
[KOITP] 가장 먼 두 도시자료구조 및 알고리즘/문제풀이 2017. 1. 17. 08:07
출 처 : http://koitp.org/problem/FARTHEST_CITY/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB14060 (43%)59문제N개의 도시가 있고, 임의의 두 도시 사이에는 항상 도로가 있다. 도시는 1번부터 N번까지 차례대로 번호가 매겨져있다. a번 도시에서 b번 도시로 가는 도로의 길이와 b번 도시에서 a번 도시로 가는 도로의 길이가 다를 수 있다. 어떤 도시에서 다른 도시로 가는데, 직접 연결된 도로를 통해 가는 것보다, 다른 도시들을 거쳐가는 것이 좋을 때가 있다. a번 도시에서 b번 도시로 가는 거리란, a번 도시에서 하나 혹은 여러 도로를 거쳐 b번 도시로 가는 최단 거리를 의미한다. 마찬가지로 a번 도시에서 b번 도시로 가는 ..
-
[KOITP] 군사 도로망(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 16. 18:23
출 처 : http://koitp.org/problem/MILITARY_ROAD_NETWORK/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수2.0 초256 MB394 (10%)2문제어떤 나라는 NN개의 도시로 구성되어 있다. 도시들을 연결하는 도로들이 있는데, 도로라는 것은 서로 다른 두 도시를 연결하는 기능을 하며, 양방향 통행이 가능하고 하나의 도시 쌍에 대해서는 최대 하나의 도로만이 존재 가능한 것으로 가정한다. 이 나라는 몇 년간 전쟁을 치르고 있어서 많은 도로가 파괴된 상태이다. 이제 도로들을 정비하여 모든 쌍의 도시가 단 하나의 길(길은 이어서 갈수 있는 도로들을 말함)로 연결되도록 하고 싶다. 군사적인 이유로, 두 도시를 연결하는 길이 두 가지 이상 존재하는 것을 원하지..
-
[KOITP] 워프자료구조 및 알고리즘/문제풀이 2017. 1. 16. 08:02
출 처 : http://koitp.org/problem/SDS_PRO_10_3/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1895235 (12%)165 문제우주에 N개의 행성이 있다. 어떤 행성쌍에는 워프장치가 존재하는데 ai행성에서 bi행성으로 워프를 타고 ci시간만에 이동할 수 있다. 이때, 워프장치가 설치되어 있는 형태는 ai < bi를 만족한다. 또한, 행성 간의 이동은 오직 워프장치를 통해서만 할 수 있다. 1번 행성에 N번 행성까지 이동하려고 할 때, 최소로 드는 시간을 구하여라.입력첫 번째 줄에 행성의 개수 N과 워프장치의 개수 M이 공백으로 분리되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 500,000) 두 번째 줄부터 각 워프장..
-
[KOITP] 보물섬자료구조 및 알고리즘/문제풀이 2017. 1. 16. 08:02
출 처 : http://koitp.org/problem/SDS_PRO_4_3/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB2632473 (18%)354 문제강희는 악마의 바다에 어마어마한 보물이 숨겨져 있는 보물섬이 있다는 정보를 입수했다. 하지만 악마의 바다에는 해류가 매우 복잡하게 흐르고 있기 때문에 강희는 좀처럼 보물을 얻고 돌아올 길을 찾기가 힘들어 여러분에게 도움을 요청했다. 강희가 악마의 바다에서 보물을 찾아올 수 있는 최단 시간을 계산하자. 악마의 바다에는 1번부터 N번까지 섬이 N개가 있으며, 서로 다른 섬들을 연결하는 해류가 M개 존재한다. 해류는 한 방향으로만 흐르며 어떤 두 쌍을 잇는 해류가 여러개 존재할 수도 있다. 강희는 현재 1번 섬에 있..
-
[KOITP] 유령선자료구조 및 알고리즘/문제풀이 2017. 1. 16. 07:59
출 처 : http://koitp.org/problem/SDS_PRO_4_1/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB2193378 (17%)323 문제강희는 정신을 차려보니 낯선 유령선에 납치당해 있었다. 강희는 유령들이 자고 있는 낮 시간에 몰래 유령선에 있는 구명보트를 이용해 탈출하려고 한다. 유령선의 갑판은 동일한 크기의 정사각형 모양 판자가 가로로 W개, 세로로 H개 이어진 모양으로 되어 있다. 강희는 현재 서 있는 위치에서 상하좌우로 움직일 수 있다. 유령선은 매우 낡았기 때문에 강희가 딛고 있는 판자를 벗어나면 판자가 부서지고 만다. 심지어 이미 부서져 있는 판자도 존재한다. 물론 강희는 유령이 아니기 때문에 부서진 판자는 걸어서 지나갈 수 없다...