Algorithm

최소 비용 트리 (Least Spanning Tree)를 공부하다가 풀게 된 문제이다. 이 문제에서 크루스칼 알고리즘을 사용하여 풀었다. 최소 비용 트리는 보통 프림 알고리즘이나 크루스칼 알고리즘을 사용하여 푼다. 그 중 크루스칼 알고리즘에 대해 먼저 다뤄보겠다.

백준 solved.ac 기준 골드4에 배치된 문제이다.문제링크: https://www.acmicpc.net/problem/1744문제를 살펴보자.문제를 간단히 요약하자면 수열이 주어졌을 때 수열에서 인접한 두 수를 한 번만 묶을 수 있다.이렇게 묶인 두 수는