Analysis & Visualization/Python1 탐욕적 기법 알고리즘 - KRUSKAL 최소비용 신장트리(MST) 문제에서 현재 선택할 수 있는 가중치 중 가장 작은 가중치를 가진 간선을 선택하는 방법(탐욕적인 해). 그와 동시에 간선을 추가했을 때 사이클이 생기면 안된다. MST(minimum spanning tree)란 가중치 그래프 G = (V, E) 의 모든 신장트리 중에서 간선들의 합이 최소인 트리. ex) 도시 10곳을 최소비용으로 모두 거치는 방법 # 서로소 집합 class disjoinSets: def __init__(self, n): self.parent = [-1]*n self.set_size = n def find(self, id): while(self.parent[id] >= 0): id = self.parent[id] return id def union(self, s.. 2022. 6. 8. 이전 1 다음