[Disjoint Set] BOJ 25579 터트려라 풍선
2023. 4. 23. 13:09
Algorithm/MST
문제 https://www.acmicpc.net/problem/25579 25579번: 터트려라 풍선 방구석 독거 코더가 된 병우를 안타까워한 친구들이 병우에게 여자친구를 소개해 주었고, 둘은 놀이공원에 놀러 가게 되었다. 놀이공원 벤치에서 꽁냥꽁냥을 하던 병우는 맞은편에 풍선 다트 www.acmicpc.net 접근 방법 일반적으로 생각했을 때 떠오르는 방법인 각 풍선을 하나씩 터트린다는 방법으로 점수계산을 수행하면 구현이 매우 빡세진다. 구간이 계속해서 변동되고, 합과 결과도 계속 관리해주어야 하기 때문이다. 따라서 이를 역으로 생각해보자. 모두 터져있는 상태에서 터트린 순서의 역순으로 풍선이 생성된다고 가정하는 것이다. 풍선을 생성시킬 때 마다. 생성시킨 풍선의 양 옆에 다른 풍선이 생성되어 있는가를..
최소 신장 트리(Minimum Spanning Tree) - 5
2023. 4. 9. 17:23
Algorithm/MST
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..
최소 신장 트리(Minimum Spanning Tree) - 4
2023. 4. 9. 15:59
Algorithm/MST
Kruskal 알고리즘의 개요 이전에 알아보았던 Kruskal 알고리즘은 다음과 같은 방식을 통해 동작한다고 했다. $A = \emptyset$인 집합을 선언한다. 모든 간선들을 가중치 $w(u, v)$에 대해 오름차순으로 정렬시킨다. 이후 정렬된 간선들을 하나씩 선택하여 사이클이 형성되는지 확인하고, 사이클이 형성되지 않는다면 $A$에 포함시킨다. 3번의 수행을 $|A| = N - 1$이 될 때 까지 수행한다.($N$은 정점의 개수) 이때 사이클이 형성되는지를 어떻게 알 수 있는지를 아직 확인하지 않았다. 이번 글에서는 사이클을 어떻게 판별할 수 있는지에 대해 알아볼 것이다. 접근 다음과 같은 상황을 가정해보자 간선들의 오름차순 정보와 $A$를 무시하고 그래프만 놓고 보았을 때. 다음과 같이 생각할 수..
최소 신장 트리(Minimum Spanning Tree) - 3
2023. 4. 8. 17:53
Algorithm/MST
지금까지 정리 최소 신장 트리는 어떤 무방향 가중치 그래프가 주어졌을 때, 그 그래프의 모든 정점을 연결하면서, 가중치의 합이 최소가 되는 간선의 부분집합으로 정의했다. 최소 신장 트리를 구하는 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)- 2
2023. 4. 8. 14:28
Algorithm/MST
최소 신장 트리(Minimum Spanning Tree) - 1 최소 신장 트리(Minimum Spanning Tree) - 1 최소 신장 트리 문제 아래와 같은 그래프가 있다고 가정하자. 각각의 노드를 도시로, 간선을 도로로 생각해보자. 우리는 정부에서 예산을 받아 해당 도시들을 모두 이어주는 도로들을 만들어야 sehun5515.tistory.com 지금까지의 내용 요약 최소 신장 트리는 어떤 무방향 가중치 그래프가 주어졌을 때, 그 그래프의 모든 정점을 연결하면서, 가중치의 합이 최소가 되는 간선의 부분집합으로 정의했다. 최소 신장 트리를 구하는 Generic한 알고리즘은 아래와 같은 과정을 거친다. 먼저 $A = \emptyset$ 인 집합을 선언한다. 이 집합 $A$에 대해 안전한 간선을 하나 찾..
최소 신장 트리(Minimum Spanning Tree) - 1
2023. 4. 7. 18:48
Algorithm/MST
최소 신장 트리 문제 아래와 같은 그래프가 있다고 가정하자. 각각의 노드를 도시로, 간선을 도로로 생각해보자. 우리는 정부에서 예산을 받아 해당 도시들을 모두 이어주는 도로들을 만들어야 한다. 지금 주어진 간선들은 도로 후보군들로, 각 도로를 건설하는데 드는데 소비되는 예산이 표시되어있다. 언제나 예산은 부족하기 때문에 우리는 최소의 비용으로 모든 도시를 이어줄 수 있도록 하는 도로 후보군들을 뽑아야 한다. 이때, 드는 예산의 최소값은 얼마인가? 이것에 대한 정답은 아래와 같이 간선을 연결하는 경우이며, 총 예산은 37이 된다. 이때 진하게 칠해져 있는 노드들과 간선의 집합을 통틀어 최소 신장 트리(Minimum Spanning Tree - MST)라고 부른다. MST의 정의 MST의 정의는 심플하게 설..
[백준][BOJ] 27958 사격 연습
2023. 4. 6. 22:05
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/27958 27958번: 사격 연습 N×N 크기의 보드 판이 존재하며, 1개 이상의 표적이 존재한다. 한 학생은 사격을 연습하고 있으며, 1번부터 K번까지 K개의 총알을 가지고 있다. 학생은 총 K번의 사격을 진행하며, 1번부터 K번까지 www.acmicpc.net 문제 접근 N의 개수가 적은것으로 보아 브루트포스나 백트렉킹 유형의 가능성이 높아보인다. 예시를 볼 때, 그리디, 또는 DP적으로 생각해보아도 무언가 딱히 규칙성이 있어보이진 않았다. 그래서 브루트포스 유형으로 생각을 하고 접근하였다. N이 최대 8까지 올라갈 수 있고, 사격 횟수 K는 최대 5번까지이다. 이때 동일한 레인에서 쏴도 상관없다라는 설명이 있으므로 동일한 레인에 K번 ..
최단 거리 알고리즘 - Floyd - Warshall 알고리즘
2023. 3. 30. 23:05
Algorithm/최단 거리
Floyd - Warshall 알고리즘 이전에 각각 살펴봤던 Dijkstra, Bellman - Ford 알고리즘은 시작 지점이 존재하고, 해당 지점에서 각 노드로의 최단 경로를 구하는데 사용하는 알고리즘이다. Floyd - Warshall 알고리즘은 모든 노드에 대해서 각 노드에 대한 최단 거리를 구하는 알고리즘이다. 쉽게 말하자면 모든 노드에 대하여 Dijkstra나 Bellman - Ford를 돌려보았다고 생각하면 좋다. 다만 구현 방법은 순수 DP를 사용한다는 것이 차이점이다. Floyd - Warshall 알고리즘 역시 음의 가중치가 존재해도 사용이 가능하며, Bellman - Ford와 동일하게 음수 사이클이 존재한다면 사용할 수 없다. Floyd - Warshall 알고리즘의 원리 DP를 사..
최단 거리 알고리즘 - Bellman - Ford 알고리즘
2023. 3. 30. 21:54
Algorithm/최단 거리
들어가며 이전에 보았던 다익스트라는 하나의 정점에서 다른 정점까지의 모든 최단 경로를 구하는데 $O((V + E) \log V)$라는 강력한 성능을 보여주었다. 하지만 문제점이 있는데 음의 가중치가 존재하는 경우 제대로 된 값을 구할 수 없다는 것이다. 이는 그리디 알고리즘의 허점과도 연관되는데 아래와 같은 간단한 그래프를 통해 알아보자. 해당 그래프에서 1부터 시작한다고 가정할 때 최단 경로는 5가 된다. 하지만 다익스트라를 사용할 시 6이 되는데 그리디하게 1번과 인접한 곳의 가중치가 각각 7, 6으로 가중치가 더 적은 6을 먼저 갱신해버리기 때문이다. 이러한 문제를 해결하기 위해서는 이미 갱신해버린 값이어도 다시 한번 검사를 해보는 방식이 필요한데 이런 방식을 구현한 알고리즘이 Bellman-For..
최단 거리 알고리즘 - 다익스트라 알고리즘
2023. 3. 30. 20:39
Algorithm/최단 거리
최단 거리 최단 거리 또는 최단 경로(Shortest Path)는 일반적으로 그래프상에서 이루어지는 개념이다. 그래프에서 한 노드를 기준으로 하여 다른 노드까지 이동하는데 걸리는 시간이 가장 적은 경로가 최단 경로 또는 최단 거리가 될 것이다. 이때 이동하는데 걸리는 시간을 수치적으로 나타낸 것이 가중치(weight)이고 최단 경로 문제는 다음과 같이 정의할 수 있을 것이다. 어떤 노드 $V_i$ 에서 다른 노드 $V_j$ 로 이동할 때 드는 가중치 $W$가 최소가 되는 경로를 구하는 문제 활용처와 방법론 최단 경로 알고리즘의 활용은 매우 무궁무진하다. 일상적으로 가장 가까이서 찾아볼 수 있는 최단 경로 알고리즘의 활용처는 네비게이션이 될 것이다. 거리의 교차점을 하나의 노드로, 도로를 간선으로 추상화한..