데이터 엔지니어

문제링크: https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 설명 - N: 컴퓨터의 개수 - M: 연결하는 선의 개수 - (a, b, c) M개 주어짐 (c=비용) 위와 같은 입력이 주어졌을 때, 모든 컴퓨터를 연결할 수 있는 최소 비용을 찾는 문제입니다. 풀이 MST를 찾는 문제입니다. MST는 Minimum Spanning Tree 최소 신장트리를 뜻하며, 모든 정점을 잇는 최소 비용의 트리입니다. MST를 찾기 위해서 크루스칼(kruskal) 알고리즘을 사용합니다. 크루스칼 알고리즘 1. 비용순으로 edge들을 정렬한다. 2..

문제링크: https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 설명 - N: 도시의 개수 - M: 버스의 개수 - (출발 도시, 도착 도시, 버스 비용) M개 - 시작도시, 끝도시 위와 같은 입력이 주어졌을 때, 시작도시부터 끝도시까지 가는 최소비용을 구하는 문제입니다. 풀이 문제를 보자마자 최소거리를 구하는 알고리즘들을 떠올렸습니다. 코테에서 주로 나오는 그래프 알고리즘들은 아래와 같습니다. 이 문제에는 시..