반응형 크루스칼2 [C/C++] 백준 #1922 네트워크 연결(크루스칼) 컴퓨터 네트워크를 공용망에 연결하지 않고, 체인 형태로 연결할 때, 최소 비용으로 모든 컴퓨터를 다 연결하고자 합니다. 컴퓨터간 연결하는 비용이 제시되었을 때, 이를 이용해서 가장 최소 비용으로 컴퓨터간 연결을 모두 합니다. 대표적인 최소 간선 비용 트리(MST : Minimum Spanning Tree) 문제입니다. 최소 간선 비용 트리를 만드는 방법은 여러가지가 있지만, 보편적으로 많이 사용되는 것이 크루스칼 알고리즘과 프림 알고리즘입니다. 그 외에도 몇가지 더 있죠. 집합 개념을 사용해서 집합갠 최소 비용 간선을 선택할 수도 있고요. 크루스칼 알고리즘과 같이 간선 가중치를 모두 정렬한 후에 최소 비용 간선을 선택하면서 집합을 늘려가는 방법도 있습니다. 제 경우에는 크루스칼 알고리즘을 이용했습니다. .. 2022. 11. 9. [C/C++] 백준 #1647 도시 분할 계획(크루스칼 알고리즘) 이번 문제는 전형적인 최소 스패닝 트리(Minimum Spanning Tree) 문제입니다. 최소 스패닝 트리를 구하는 방법중 대표적인 방법은 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘이 있습니다. 둘 중에 어떤 알고리즘이 좋은가를 할 때에는 제 개인적으로는 크루스칼 알고리즘이 더 좋습니다. 알고리즘 효율은 프림 알고리즘은 \(O(E \log E)\)이고 크루스칼 알고리즘은 \(O(E \log E)\) 로 비슷합니다. 물론 우선순위큐를 잘 만들면 프림 알고리즘은 \(O(E \log V)\) 까지도 가능하지만, 사실상 의미가 없습니다. \(E\) 자체의 최대치가 \(V(V-1)/2\) 이므로 로그(log) 함수 안에서는 아무런 의미가 없습니다. 개인적으로 크루스칼 알고리즘을 더 선호하는 .. 2022. 9. 20. 이전 1 다음 728x90
