코딩하는 해맑은 거북이

해당 글은 백준 4485번 '녹색 옷 입은 애가 젤다지?' 문제를 다룬다.문제https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지?젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주www.acmicpc.net 설명(0, 0)에서 (n-1, n-1)까지 이동할 때 최소 비용으로 가야하므로 최단 경로를 구하는 알고리즘 중 다익스트라를 활용하면 된다. 이때 주의할 점은 heapq를 사용하므로 heappush할 때 비용이 먼저 위치하도록 한다! 코드import heapq dx = [-1, 1, 0, 0] dy = [0,..

해당 글은 백준 1647번 '도시 분할 계획' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 설명 해당 문제는 크루스칼 알고리즘으로 해결할 수 있다. 분리된 두 마을을 만들고, 그 사이에 길은 없애야 한다. 여기서 분리된 마을안에는 최소 1개의 집만 존재해도 되므로 크루스칼 최소신장 트리를 만들고, 마지막 길만 없애주면 분리된 두 마을을 만드는 최소길이 값이 나온다. 코드 import..

해당 글은 백준 10159번 '저울' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 설명 해당 문제는 최단 경로 찾기 문제 중 플로이드-워셜 알고리즘을 활용하여 해결할 수 있다. 여기서 그래프는 이동 가능할 때 True, 이동 불가능 할 때 False로 만들었다. 플로이드-워셜 알고리즘으로 i->j로 이동할 때, k를 거쳐서 이동가능한 경우도 True로 변경해준다. 마지막 출력으로 i->j로 이동..

해당 글은 백준 2623번 '음악프로그램' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 설명 해당 문제는 위상 정렬 알고리즘으로 해결할 수 있다. m명의 PD가 정한 순서들을 모두 반영할 수 있는지 여부는 result 리스트의 갯수가 가수의 수(n)인지를 파악할 수 있다. 코드 from collections import deque n, m = map(int, input().split()) indegr..

해당 글은 백준 4386번 '별자리 만들기' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 설명 해당 문제는 최소 신장 트리를 구하는 알고리즘으로 해결할 수 있다. 여기서는 크루스칼 알고리즘을 사용하였고, graph에 두 점 사이의 거리를 저장하고, 오름차순으로 정렬한 후 계산하였다 코드 import math n = int(input()) point = [] for _ in range(n): x, y = map(float,..

해당 글은 백준 1516번 '게임 개발' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 설명 해당 문제는 순서가 정해져있는 일련의 작업을 차례대로 수행할 때 사용하는 위상 정렬 알고리즘으로 해결할 수 있다. 저장할 그래프는 방향이 있으므로 노드 A에서 노드 B로 갈 때의 간선만 저장한다. 또한, 결과값을 담는 result는 time 리스트를 깊은복사하여 사용한다. 코드 from collections import..