출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 43, p 397 크루스칼 알고리즘을 이용해 최소 비용의 신장 트리를 탐색했습니다. 최종 반환해야 할 답이 절약할 수 있는 최대 금액이므로, 전체 도로에 가로등을 설치하는데 드는 비용을 total_cost로 저장하고, 최소 신장 트리를 만들었을 때 가로등을 설치하는데 드는 비용을 min_cost로 저장하여 둘의 차를 반환했습니다. import sys # 입력 받아오기 inputs = list(map(int, sys.stdin.read().split())) # 집의 수 N = inputs[0] parent = [0] * N for i in range(N): parent[i] = i # 도로의 수 M = inputs[1] # (도로의 길이, 도로..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 42, p 395 비행기를 '최대' 몇 대 도킹할 수 있는지 출력해야 하므로 이진 탐색을 이용해 풀이했습니다. 먼저 도킹할 수 있는 비행기의 최소 대수를 1대, 최대 대수를 게이트의 개수인 G대로 설정합니다. 이후 중간값을 계산하고, 이 중간값만큼의 비행기를 도킹할 수 있는지 확인합니다. 비행기를 순서대로 도킹한다고 했으므로, 중간값 개수만큼의 도킹 정보를 가져오고, 이를 dock라는 함수에 전달합니다. dock 함수는 도킹 정보 리스트를 받아 모든 비행기를 도킹할 수 있으면 True, 아니면 False를 반환하는 함수입니다. 이는 힙을 이용해 구현했는데, 파이썬의 heapq는 Min Heap이므로, Max Heap으로 사용하기 위해 각 el..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 41, p 393 서로소 집합을 이용해 여행 계획 안에 있는 여행지들이 모두 같은 집합에 속하면 예행 계획이 가능한 것으로, 그렇지 않으면 불가능한 것으로 풀이했습니다. 연결된 도시들의 정보가 리스트가 아닌 행렬로 주어지므로 행렬의 값 중 0이 아니라 1인 부분의 좌표를 통해 연결된 도시들의 정보를 담은 리스트 links를 생성했습니다. 이를 이용해 서로소 집합 알고리즘을 수행하고, 계획에 있는 도시들이 속한 집합을 확인해 이들이 모두 같으면 YES, 아니면 NO를 출력했습니다. import sys # 입력 받아오기 inputs = list(map(int, sys.stdin.read().split())) # 여행지의 수 N = inputs[0..

1. 개선된 서로소 집합 알고리즘 - 서로소 집합Disjoint Sets: 공통 원소가 없는 두 집합 - 서로소 집합 자료 구조 = union-find 자료구조 (1) 개선된 서로소 집합 알고리즘 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b]..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 40, p 390 프로그래머스의 가장 먼 노드 문제와 매우 유사한 문제였습니다. 마찬가지로 다익스트라 알고리즘으로 풀이했습니다. 다익스트라 알고리즘 코드대로 graph, distance를 초기화하고 입력에 맞게 graph 정보를 저장했습니다. 헛간을 잇는 통로가 양방향이고, weight가 따로 없기 때문에 이 부분만 기존 코드를 수정했습니다. 이후 다익스트라 알고리즘을 실행하여 distance를 구한 뒤, 가장 먼 헛간의 최단거리만큼 떨어진 헛간들 중 헛간 번호가 가장 작은 것, 가장 먼 헛간의 최단거리, 가장 먼 헛간의 최단거리만큼 떨어진 헛간들의 개수를 순서대로 반환했습니다. import sys import heapq INF = int(1..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 39, p 388 다익스트라 알고리즘을 활용해 풀이했습니다. 우선 입력을 받아 하나의 테스트 케이스는 N*N 리스트로 정리하고, 각 테스트 케이스를 spaces라는 리스트에 저장했습니다. 화성 탐사 기계는 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다고 했으므로, 그래프의 인접한 노드 대신 상하좌우의 좌표를 탐색하며 풀이했습니다. 이때 N*N 리스트 밖으로 나가 IndexError가 발생하는 것을 방지하기 위해 인덱스가 0~N-1 사이인지 확인해주었습니다. 마지막으로 가장 위 칸인 (0,0)을 지나는데도 에너지가 소모되므로, 다익스트라 알고리즘이 끝난 후에 (0,0)을 지나는데 소모되는 에너지를 더해주었습니다. import fileinput ..