MST2 [알고리즘] Prim`s algorithm. MST 구하는 2번째 방법. 프림 반갑습니다. 이번엔 O(ElogV) 시간복잡도를 가지는 Prim알고리즘에 대해서 알아보겠습니다. 이건 음.. heap을 알아야 하는데, 힙구조를 가지는 priority_queue를 사용할 수 있으면 좋습니다. 없으면 kruskal이 구현하기 더 낫습니다. Kruskal VS Prim 결과부터 말하면 Edge가 많으면 Prim, Edge가 적으면 Kruskal이 좀 더 좋습니다. (이론상) Kruskal은 sort과정에 O(ElogE)이 피할 수 없기에 E에 영향을 받고, Prim은 O(ElogV)입니다. 이미 방문된 지점은 다시 방문되지 않기에 pq의 push나 pop과정이 없어서 그렇습니다. 근데 MST를 찾는다는건 기본적으로 V < E니까 쓰겠죠...? 근데 그냥 편한대로 합시다. .. 2021. 10. 2. [자료구조] MST를 구할 때 사용하는 크루스칼 알고리즘(Kruskal) 설명에 앞서, Union - Find 연산에 대해서 학습을 해야하는데, 이 부분은 제가 봤던 유튜브로 대체하겠습니다. https://www.youtube.com/watch?v=eTaWFhPXPz4 이것과 Optimized Union/FInd를 보시고 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 이 문제를 풀어서 제대로 이해했나 확인해보시면 됩니다. Kruskal 알고리즘을 왜 쓰는가? - MST를.. 2021. 9. 30. 이전 1 다음 728x90
