algorithm/data structure (1) 썸네일형 리스트형 Kruskal's MST algorithm Kruskal's MST algorithm은 Minimum Spanning Tree를 구하는 알고리즘 중 하나이다. Minimum Spanning Tree는 우리말로 번역하면 최소 신장 트리라고 하는데, 여기서 신장(伸張)은 펼 신, 길 장, 이는 뻗어 나간다는 의미가 있다. 고로 모든 노드를 거치는 나무, 뻗어 나가는 나무, 생성 나무라고도 한다. Kruskal's MST algorithm은 탐욕적인 방법(Greedy method)을 이용하고, 순간마다 제일 나은 선택을 한다. 그러나 제일 나은 선택이라고 생각했던 해답들을 모아서 최종적인 해답을 만들었다고 해서, 그 해답이 전체적인 관점에서 최적이라는 보장은 없다. 따라서 이 알고리즘은 항상 최적의 해답을 주는지를 반드시 점검해야 하는데, 다행히 Kr.. 이전 1 다음