맷돌로그

오늘은 크루스칼(Kruskal) 알고리즘과 이를 구현하기 위해 필요한 개념인 Union Find에 대해 알아보겠습니다. 우선 이를 이해하기 위해서는 Minimum Spanning Tree에 대한 이해가 필요합니다. Minimum Spanning Tree (최소 신장 트리)와 크루스칼 알고리즘에 대해서는 지난 포스팅에서 상세하게 설명했으니 참고 바랍니다. Kruskal Algorithm : 크루스칼 알고리즘 : 음수 가중치가 없는 무방향 그래프에서 Minimum Spanning Tree를 찾는 알고리즘 그런데, Minimum Spanning Tree를 찾을 때에는 사이클이 발생하면 안된다고 했습니다. 그럼 사이클이 발생했는지는 어떻게 알 수 있을까요? 사이클이 발생하는 경우는 같은 그래프에 속한 두 노드를..

프로그래머스 문제를 풀다가 크루스칼 알고리즘이라는 것과 마주치게 되었다. 처음 접하는 알고리즘이라 생각했지만, 이에 대해 찾아보면서 나는 기억하게 된다. 1학년 시절 이산수학 시간에 크루스칼 알고리즘과 프림 알고리즘에 대해 배웠다는 것을.. 손과제도 했었지.. 그 때는 정말로 이해가 안됐어.. 3년이 지난 지금에서야 다시 정리해보려 한다. Minimum Spanning Tree : 최소 신장 트리, 최소 스패닝 트리 : 가중치 무방향 그래프에서 모든 정점을 최소 비용으로 연결할 수 있는 방법 위와 같이 간선에 가중치가 있고, 방향이 없는 그래프를 가중치 무방향 그래프라고 합니다. 그리고 그래프 위의 모든 정점을 최소 비용으로 탐색하는 방법을 찾고자 합니다. 이 때 생각해볼 수 있는 것은, 최소 비용이 되..