class 5https://www.acmicpc.net/problem/1197  # 문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. # 예제입력 : 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고..

이번 챕터에서는 탐욕알고리즘과 이를 이용하는 프림, 크루스칼, 다익스트라 알고리즘을 정리해보려고 한다. 한 게시물에 정리하기에는 내용이 너무 많아서 나눠서 정리할 예정이다. 목차는 다음과 같다. Greedy Approach (GA, 탐욕 알고리즘) Minimum Spanning Tree (MST, 최소 신장 트리) GA - 1. Prim's algorithm (프림 알고리즘) 1. Greedy Approach (탐욕 알고리즘) 동적 프로그래밍이 작게 쪼개고 재귀를 통해 작은 것들부터 해결해나가는 기법이었다면, 탐욕 알고리즘은 작게 나누지 않고 그때그때 탐욕스러운 (가장 이익이 되는) 선택을 해나가는 알고리즘이다. 접근 방식은 다음과 같다. 선택 과정 가장 가까운 노드들 중에서 현재 고려사항을 최고로 만족..