문제 https://www.acmicpc.net/problem/25579 25579번: 터트려라 풍선 방구석 독거 코더가 된 병우를 안타까워한 친구들이 병우에게 여자친구를 소개해 주었고, 둘은 놀이공원에 놀러 가게 되었다. 놀이공원 벤치에서 꽁냥꽁냥을 하던 병우는 맞은편에 풍선 다트 www.acmicpc.net 접근 방법 일반적으로 생각했을 때 떠오르는 방법인 각 풍선을 하나씩 터트린다는 방법으로 점수계산을 수행하면 구현이 매우 빡세진다. 구간이 계속해서 변동되고, 합과 결과도 계속 관리해주어야 하기 때문이다. 따라서 이를 역으로 생각해보자. 모두 터져있는 상태에서 터트린 순서의 역순으로 풍선이 생성된다고 가정하는 것이다. 풍선을 생성시킬 때 마다. 생성시킨 풍선의 양 옆에 다른 풍선이 생성되어 있는가를..

Kruskal 알고리즘의 정리 Kruskal 알고리즘은 다음과 같은 방식을 따른다. 가중치에 대해서 간선들을 정렬한다. 각 정점에 대한 Union-Find 자료구조를 초기화시킨다. 정렬된 간선들을 하나씩 택하면서 find를 통해 동일 집합에 포함되는지를 판단한다. 이때, 동일 집합이 아니라면, 가중치의 합에 해당 간선의 가중치를 더하고, 두 정점을 합친다(Union) Union-Find를 어떻게 구현하는지는 앞서 설명한 글이 있으니 그것을 참고한다. Kruskal 알고리즘의 구현 // 알고리즘 - 최소 신장 트리 // 크루스칼 알고리즘 import java.util.Arrays; public class Main { // O(E logE) static int[] parents; static int[] si..

Kruskal 알고리즘의 개요 이전에 알아보았던 Kruskal 알고리즘은 다음과 같은 방식을 통해 동작한다고 했다. $A = \emptyset$인 집합을 선언한다. 모든 간선들을 가중치 $w(u, v)$에 대해 오름차순으로 정렬시킨다. 이후 정렬된 간선들을 하나씩 선택하여 사이클이 형성되는지 확인하고, 사이클이 형성되지 않는다면 $A$에 포함시킨다. 3번의 수행을 $|A| = N - 1$이 될 때 까지 수행한다.($N$은 정점의 개수) 이때 사이클이 형성되는지를 어떻게 알 수 있는지를 아직 확인하지 않았다. 이번 글에서는 사이클을 어떻게 판별할 수 있는지에 대해 알아볼 것이다. 접근 다음과 같은 상황을 가정해보자 간선들의 오름차순 정보와 $A$를 무시하고 그래프만 놓고 보았을 때. 다음과 같이 생각할 수..

지금까지 정리 최소 신장 트리는 어떤 무방향 가중치 그래프가 주어졌을 때, 그 그래프의 모든 정점을 연결하면서, 가중치의 합이 최소가 되는 간선의 부분집합으로 정의했다. 최소 신장 트리를 구하는 Generic한 알고리즘은 아래와 같은 과정을 거친다. 먼저 $A = \emptyset$ 인 집합을 선언한다. 이 집합 $A$에 대해 안전한 간선을 하나 찾은 후, 이를 $A$에 더한다(Union) $A$에 속한 간선의 개수가 $N - 1$개가 될 때 까지 2번을 반복한다. 이때 "안전하다(safe)" 라는 개념을 아래와 같이 정의했었다. 어떤 MST의 부분집합 $A$에 대하여 $A \cup \{(u, v)\}$를 수행할 때 그 결과 역시 어떤 MST의 부분집합이 될 때 이 간선 $E(u, v)$가 $A$에 대하..

최소 신장 트리(Minimum Spanning Tree) - 1 최소 신장 트리(Minimum Spanning Tree) - 1 최소 신장 트리 문제 아래와 같은 그래프가 있다고 가정하자. 각각의 노드를 도시로, 간선을 도로로 생각해보자. 우리는 정부에서 예산을 받아 해당 도시들을 모두 이어주는 도로들을 만들어야 sehun5515.tistory.com 지금까지의 내용 요약 최소 신장 트리는 어떤 무방향 가중치 그래프가 주어졌을 때, 그 그래프의 모든 정점을 연결하면서, 가중치의 합이 최소가 되는 간선의 부분집합으로 정의했다. 최소 신장 트리를 구하는 Generic한 알고리즘은 아래와 같은 과정을 거친다. 먼저 $A = \emptyset$ 인 집합을 선언한다. 이 집합 $A$에 대해 안전한 간선을 하나 찾..

최소 신장 트리 문제 아래와 같은 그래프가 있다고 가정하자. 각각의 노드를 도시로, 간선을 도로로 생각해보자. 우리는 정부에서 예산을 받아 해당 도시들을 모두 이어주는 도로들을 만들어야 한다. 지금 주어진 간선들은 도로 후보군들로, 각 도로를 건설하는데 드는데 소비되는 예산이 표시되어있다. 언제나 예산은 부족하기 때문에 우리는 최소의 비용으로 모든 도시를 이어줄 수 있도록 하는 도로 후보군들을 뽑아야 한다. 이때, 드는 예산의 최소값은 얼마인가? 이것에 대한 정답은 아래와 같이 간선을 연결하는 경우이며, 총 예산은 37이 된다. 이때 진하게 칠해져 있는 노드들과 간선의 집합을 통틀어 최소 신장 트리(Minimum Spanning Tree - MST)라고 부른다. MST의 정의 MST의 정의는 심플하게 설..