My Tech Blog (크루스칼)

📑 1. 문제설명💡 2. 접근방식이 문제는 너무 어려워서 스스로 풀기 힘들어서 검색의 도움을 받음.주어진 문제는 그래프 이론의 최소 신장 트리(MST, Minimum Spanning Tree) 문제이다. 이 문제를 풀기 위해 필요한 전제지식- Union-Find(유니온 파인드) 자료구조- Kruskal's Algorithm (크루스칼) 알고리즘 Kruskal's Algorithm (크루스칼 알고리즘)크루스칼 알고리즘은 위에 말한 최소신장트리(MST)를 구하는 알고리즘이다. 문제의 분류 답게 greedy알고리즘으로 결정의 순간마다 최선의 결정을 함으로서 최종적인 답을 구하는 방식으로 모든 정점을 최소 비용으로 연결할 수 있게 해준다.크루스칼 알고리즘의 핵심은 모든 간선을 가중치 기준(여기서는 다리 개설..