크루스칼3 [C/C++] 백준 #2887 행성 터널(크루스칼 알고리즘) 이번 문제는 크루스칼 알고리즘을 이용해서 풀었습니다. https://www.acmicpc.net/problem/2887 하지만, V개의 행성을 모두 연결한다면, \(V(V-1)\)만큼의 간선이 생기므로, 정렬을 할 때, 주어진 V값에 대해서 느려질 수 있습니다.간선의 갯수는 최소 비용 신장 트리(Minimum Spanning Tree)를 프림 알고리즘을 이용하든, 크루스칼 알고리즘을 이용하든 모두 시간 복잡도가 주어진 V값의 최대치라면, 시간초과가 됩니다. \(E = V(V-1)\)이 된다면, 프림 알고리즘 상에서는 \(O(E \log V) = O(V^2 \log V)\), 크루스칼 알고리즘 상에서는 \(O(E \log E) = O(V^2 \log V\) 형태가 되겠죠. 물론 프림 알고리즘을 구현할 .. 2024. 8. 25. [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 다음
