알고리듬

문제오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  visited[R] 입력첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ ..

문제 설명n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요. 제한사항입국심사를 기다리..

문제승택이는 강을 건너려 한다.승택이는 수영을 못하기 때문에, 강에 놓인 징검다리를 밟고 건너갈 것이다.승택이는 수영은 못하지만 제자리뛰기는 정말 잘한다. 원하는 어느 곳으로든지 점프해서 바로 갈 수가 있다.승택이는 이제 강의 한쪽 변 앞에 서 있다.강엔 1번부터 시작해 2번, 3번, ... , N번 징검다리가 차례대로 놓여 있다.강의 폭이 넓은 탓에 징검다리의 수는 엄청나게 많다.이 징검다리를 모두 밟고 싶지는 않았던 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만을 밟고 가기로 했다.물론 강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너기 위해 승택이는 다음과 같은 규칙을 정했다.첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.두 번째 점프부터..

문제김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.게임 기록은 다음과 같이 생겼다.게임 횟수 : X이긴 게임 : Y (Z%)Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=8..

문제네 사람이서 2차원 평면상의 N개의 점을 이용해서 할 수 있는 놀이가 있다. 바로 각 사람이 1개씩의 점을 적절히 선택해서 변이 x축 혹은 y축에 평행한 직사각형을 만드는 일이다. 물론 그냥 만들면 재미가 없기 때문에 가로의 길이가 A 세로의 길이가 B인 직사각형을 몇 가지나 만들 수 있는지 알아보기로 했다.예를 들어 점이 A(0, 0), B(2, 0), C(0, 3), D(2, 3), E(4, 0), F(4, 3)의 6개가 있고, 만들고 싶은 직사각형이 가로가 2, 세로가 3인 직사각형이라면 (A, B, C, D), (B, D, E, F)의 두 가지 경우가 가능하다. 모든 경우의 수를 구해보자.입력첫 줄에 점들의 개수 N(5 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에 만들고 싶은 직사각형의 ..

문제 군탈 체포조(Deserter Pursuit)란 탈영병을 추적/체포하는 군인들을 말하며, 줄여서 DP 라고도 한다. 어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라는 명령이 주어졌는데, 돈을 아껴 봉지라면을 사 먹고 싶은 호열이는 활동비를 최대한 아끼면서 탈영병을 모두 잡으려고 한다. 지도는 N * N 크기의 격자로 표현된다. 지도 위에는 부대와 탈영병들의 위치가 주어지며 부대나 탈영병이 없는 나머지 칸에는 모두 톨게이트가 존재한다. 각 톨게이트에는 내야 하는 통행료가 정해져 있고 톨게이트가 있는 칸을 방문하기 위해서는 반드시 통행료를 지불해야 한다. 또한 같은 칸을 여러 번 방문해도 매번 통행료를 내야 한다. 호열이는 부대에서 출발해 탈영병을 모두 잡은 ..

문제 종강을 맞은 민준이는 고향인 마산으로 내려갈 계획을 짜고 있었다. 늘 그랬듯, 마산으로 갈 버스를 예약하려던 순간 민준이는 집으로 가는 다른 방법이 떠올랐다. 그것은 직접 지도를 보고 고향으로 가는 가장 짧은 길을 찾는 것이다. 그때, 먼저 고향으로 내려갔던 친구인 건우에게 연락이 왔다. 건우는 고향으로 내려가던 중 알 수 없는 일에 휘말려 외딴곳에 혼자 남겨지게 되었다. 건우는 유일한 구세주인 민준이에게 도움을 청한 것이었다. 그러나 마산의 남자인 민준이에게는 마산이 먼저였다. 민준이는 처량한 건우를 무시한 채 고향으로 떠나려고 했지만, 만약 고향으로 가는 길에 건우가 있다면 겸사겸사 도움을 줄 수 있을 것 같았다. 지도는 양방향 그래프 형태로 되어있다. 출발지는 1번 정점 마산은 V번 정점이다...

문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다. 하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야..