오늘은 최소 신장 트리를 만드는 알고리즘 중 Kruskal 알고리즘에 대해서 알아보겠습니다. Kruskal 알고리즘이란? Kruskal 알고리즘은 MST(최소 신장 트리)를 만드는 알고리즘 중 하나입니다. 이 알고리즘은 그리디 알고리즘을 이용하여 구현합니다. 각 간선마다의 weight를 고려하여 매순간 최소의 weight를 선택합니다. 그 후, 선택한 간선을 넣었을 때 사이클이 생긴다면 해당 간선을 버리는 방식으로 진행됩니다. 아래의 예시를 통해서 조금 더 자세히 알아봅시다. 이전에 MST를 다룬 글에서 예시로 들었던 그래프를 사용해보겠습니다. 각 간선마다 이러한 가중치를 가지는 그래프가 있다고 해봅시다. 우리는 우선, 각 가중치 순으로 정렬하여 우측에 정리해보겠습니다. 자, 이제 우리는 가장 작은 가중..
