[프로그래머스] 탐욕법 5. 섬 연결하기

문제 https://programmers.co.kr/learn/courses/30/lessons/42861?language=python3 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 최소신장트리 문제인 것 같아 검색해 보았다. MST 문제에는 크게 두 가지 방법의 해결책이 있는 듯 했다. 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복 Prim의 알고리즘의 시간 복잡도는 O(n^2) Kruskal 알고리즘의 시간 복잡도는 O(elog₂e) 그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합하고 그래프에 간선이 많이..