자료구조 및 알고리즘
-
[KOITP] 풍선자료구조 및 알고리즘/문제풀이 2017. 1. 17. 08:10
출 처 : http://koitp.org/problem/SDS_PRO_6_4/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1644385 (23%)343 문제큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다. 우리의 목표는 모든 풍선을 ..
-
[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번 섬에 있..