Sims의 문제해결 저장소

이번에도 MST 알고리즘 문제를 하나 풀어보고자 한다.https://www.acmicpc.net/problem/6497 해당문제도 MST 관련된 문제여서, 여기까지 풀어본다면 MST에 대한 개념은 충분히 잡을 수 있을 것이라 생각이 든다.해당 문제도 오리지널 MST 알고리즘을 통해서 풀 수 있는 문제다. MST 알고리즘에 관련해서 다시한번 기억해보자. 1. node, edge , value가 각각 주어지는 상황에서, 최소한의 value을 이용하여 모든 노드를 하나의 그래프에 속하도록 만드는 테스크이다.2. edge의 총 개수는 node - 1로 MST를 구성할 수 있다.3. MST는 유니온 파인드 알고리즘을 이용해서 해결할 수 있다. MST 문제를 풀때 위 내용만 기억하고 진행하면 될 것이다. 푸는 순서..

이번에는 최소 신장 트리에 대해 공부하고 정리해보고자 한다. MST란?노드와 간선이 주어지고, 간선간 가중치가 존재했을때, 모든 노드가 간선으로 연결되어 하나의 그래프를 만드는데, 그중 가중치을 가장 낮게 하는 그래프 구조를 말한다.글로만 보면 무슨 의미인지 잘 이해할 수 없다. 아래 사진을 보자. 위처럼 노드,간선, 가중치가 제공되었을때 모든 노드를 연결하는 그래프를 그리는 방법은 아주 다양하게 그릴 수 있다.위처럼 간선을 연결하여 하나의 그래프를 그릴 수 있다.하지만, 가중치의 합은 간선의 가중치 값에 따라 서로 다르게 되고, 그래프당 가중치 합은 서로 다르게 된다. 이중 가중치 합을 가장 낮게 구성하여 모든 노드를 하나의 그래프에 연결하는것이 바로 MST - 최소신장트리 가 되는것이다. 여기서 몇가..