알고리즘에서 '최소 스패닝 트리(MST, Minimum Spanning Tree)'란?

해설

MST는 N개 정점을 N-1개 간선으로 연결하되 총 비용이 최소인 트리입니다. 크루스칼 알고리즘(간선 정렬 + Union-Find)과 프림 알고리즘(우선순위 큐)으로 구합니다. 네트워크 케이블 배선, 도로 건설 비용 최소화 등에 활용됩니다.