Algorithm

[JAVA] Programmers : 배달

문제 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 해결방법 N개의 마을이 있고 각 마을을 잇는 도로가 있다. 해당 도로를 건너는데 시간은 도로마다 다르다. 이때 1번 마을에서 각 마을에 배달을 하려고 하는데 K 시간 이하인 곳만 배달이 가능해서 배달 가능한 마을의 수를 구하는 문제이다. 문제를 보자마자 다익스트라가 떠올라서 다익스트라를 이용해서 풀이를 했다. 각 마을의 도로의 정보는 인접 리스트를 이용해서 정리하고, 다익스트라 배열을 마을 개수만큼 생성한 다음 문제에서 나올 수 있..

[JAVA] Programmers : 피로도

문제 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 해결방법 오랜만에 알고리즘 풀이를 들고 왔다. 사실 알고리즘은 꾸준히 풀고 있었는데 시간도 없고 귀찮아서 글은 쓰지 않고 있었다. 문제에 대해 이야기하자면 기본적인 순열 문제라고 볼 수 있다. 순열을 이용해서 던전의 모든 방문 순서를 찾고 해당 방문 순서에 몇 개의 던전이 탐색 가능한지 확인한다. 그다음 그중에서 가장 많은 던전을 방문한 횟수를 출력하면 된다. 코드 class Solution { static int[] result; static bo..

[JAVA] 백준 17141 : 연구소 2

문제 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 해결방법 오랜만에 BFS 탐색 문제이다. 이 문제의 경우 연구소에 특정 위치에 바이러스를 놓아서 연구소 전체를 바이러스에 감염시키려는 승원이의 계획을 도와주는 문제이다. 문제에서 맵에 2로 표시된 구역이 바이러스를 놓을 수 있는 공간인데, 그 공간 중 M만큼 바이러스를 놓았을 때 연구소 전체를 감염시킬 수 있는 가장 빠른 시간을 구해야 한다. 즉, 모든 경우의 수를 탐색해야 하는 완전 탐색 문제라고도 할 수 있다. 조합을 찾을 때는 비트 마스킹을 사용해서 방문 처리를..

[JAVA] 백준 1766 : 문제집

문제 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 해결방법 위상 정렬의 대표적인 문제 중에 하나이다. 근래 위상정렬 문제를 꾸준히 풀어보고 있는데, 풀 때마다 헷갈려서 정리를 한 번 해두려고 한다. 일단 위상정렬은 Topological Sort 라고 부르며, 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하면 순서가 정해져있는 것들을 순서대로 나열하는 건데, 수학 2를 하기 전에 수학 1을 먼저 배워야 하고 그전에 기초수학을 배워야 하는..

[JAVA] 백준 1162 : 도로포장

문제 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 해결방법 1번에서 N번까지 가는 최소 시간을 출력하는 문제인데, 추가적으로 도로포장이라는 조건이 주어져있다. 포장이 가능한 횟수는 K로 주어지고, 포장을 하게 되면 해당 도시를 잇는 도로를 통과하는 시간이 0이 된다. 그래서 기본 다익스트라에 추가적으로 포장횟수를 기록해야 한다. 원래 배열은 dijk[해당 도시까지 최솟값] 을 나타낸다고 하면 이번 문제에서는 dijk[해당 도시까지 최솟값][포장 횟수] 를 사용한 2차원 ..