waca's field

# Kruskal의 MST 알고리즘 Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. 탐욕적인 방법은 알고리즘 설계에 있어 중요한 기법 중 하나다. 결정을 해야 할 때, 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택하는 방법을 말한다. 순간 순간의 최선을 선택해 최종적인 해답에 도달하는 과정인 것이다. 당시에 최적이라고 생각했던 선택들을 모은다고 해서 최종적인 결과가 최적의 해답이라는 보장은 없다. 따라서 탐욕적인 방법은 항상 검증이 필요하다. 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. Kruskal의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건을 기초로 각 단계에서 사이클을 이..