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 문제를 풀때 위 내용만 기억하고 진행하면 될 것이다. 푸는 순서..

지난번 최소신장트리의 개념을 공부했다.최소한의 개념만으로 풀어 볼 수 있는 문제가 바로 아래 링크의 문제이다.https://www.acmicpc.net/problem/1197 최소신장트리는 노드 , 간선 , 간선의 가중치가 주어지는 상황에서 최소한 간선의 가중치를 유지하며 모든 노드가 하나의 그래프에 속해있는 상태를 말한다.위 설명을 봤을때 딱 기억나는것이 한가지 있다. 바로 유니온 파인드..유니온 파인드를 이용하면 MST를 구성할 수 있다.유니온 파인드의 사이클을 점검하는 TASK, 같은 그래프에 속하는지 보는 TASK가 명확히 들어 맞는다.물론 유니온 파인드만 사용하면 풀순없지만 +@를 통해 쉽게 해결할 수있다.MST의 목표는 "최소의 간선 가중치"이다. 두 노드와 간선, 가중치가 주어질 것인데 이때..

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