백준 1197번1

• 

  [백준] 1197번 최소 스패닝 트리 - Kruskal - union find 오픈 S/W 컨트리뷰톤과 카카오 코딩 테스트를 위해 열심히 알고리즘 공부를 하는 중이다. 한 문제를 풀기 위해 여러 개의 알고리즘을 공부하게 되니 시간이 오래 걸리는 것 같다. 간단하게 코드만 정리하고 다음 공부를 하러 가야겠다. Kruskal과 Union Find - Kruskal 알고리즘 최소 신장 트리(MST)를 만들 때 사용하는 알고리즘의 종류 중 하나다. 노드가 많고 산선이 적을 때 유리하다고 하는데, 최소 신장 트리를 만드는 알고리즘 중에서는 가장 쉽기 때문에 공부를 시작했다. 시간 복잡도는 ​ O(E * logV) 모든 간선을 비용의 오름차순으로 정렬한 다음 간선을 차례대로 선택한다. - Union Find 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 여러 개의 노드가 존재.. 프로그래밍/Algorithm 2019. 9. 4.