알고리즘/백준 알고리즘

[백준 1922] 네트워크 연결

글에 개요 백준 알고리즘 1922번 "네트워크 연결" 문제입니다. 최소 스패닝 트리 문제 즉 크루스칼 알고리즘을 알면 쉽게 해결할 수 있습니다.앞서 풀었던 참고할 글 3번과 똑같은 방식으로 해결하면 되기 때문에 앞선 문제를 푸셨다면 쉽게 해결하실 수 있었을 겁니다.참고할 글 1번, 참고할 글 2번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다.크루스칼 알고리즘 (Kruskal Algorithm)를 정리한 글 내용을 꼭 보시길 추천드립니다!!!! [백준 1922] 네트워크 연결: https://www.acmicpc.net/problem/1922 참고할 글http://brenden.tistory.com/36 ([알고리즘] 크루스칼 알고리즘(Kruskal Algorithm) 정리글)http://bren..

2018. 5. 2. 10:15

알고리즘/알고리즘 개념

[알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘 (Kruskal Algorithm) ① 크루스칼 알고리즘이란? ▷ 최소 비용 신장 트리를 찾는 알고리즘입니다.▷ 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다.▷ 최소 스패닝 트리(MST, Minimum Spanning Tree)를 찾음으로서 간선의 가중치의 합이 최솟값이 되도록 하는 알고리즘이라고도 할 수 있습니다. ▶ 스패닝 트리 : 그래프에서 일부 간선을 선택해서 만든 트리. ▶ 최소 스패닝 트리 : 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리.▷ 변의 개수 E(간선), 꼭짓점의 개수 V(노드)라고 하면 이 알고리즘은 O (E log V )의 시간복잡도를 가진다. ▶ E(간선): 거리, 비용에 해당되며 선에 해당되는 부분입니다. ▶ V(노드):..

2018. 4. 28. 22:45