최소 신장 트리(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$가 최소가 되는 경로를 구하는 문제 활용처와 방법론 최단 경로 알고리즘의 활용은 매우 무궁무진하다. 일상적으로 가장 가까이서 찾아볼 수 있는 최단 경로 알고리즘의 활용처는 네비게이션이 될 것이다. 거리의 교차점을 하나의 노드로, 도로를 간선으로 추상화한..
BOJ 2110 - 공유기 설치 문제
2023. 3. 25. 15:54
Algorithm/BinarySearch
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 접근 이분 탐색의 유형인데 주어진 집의 데이터를 가지고 이분 탐색을 진행하는 것이 아니다. 문제에선 두 공유기 사이의 최대 거리를 요구하고 있기 때문에 이분 탐색으로서 우리가 찾아야 하는 값은 바로 두 공유기 사이의 최대 거리이다. 따라서 가장 작은 범위는 각 집마다 공유기를 한 개씩 설치함으로서 얻어지는 0이 되며, 가장 큰 범위는 ..
투 포인터 활용 - 프로그래머스 보석 쇼핑
2023. 3. 19. 21:33
Algorithm/Two Pointer
문제 https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 특정 구간에 모든 종류의 보석들이 포함되어 있는가를 묻는 문제이다. 보석들의 진열은 중복된 보석들이 존재할 수 있기 때문에 종류를 파악하기 위해 HashSet을 사용하였다. 또한 구간 내에 존재하는 각 보석의 종류와 그 갯수를 확인하기 위해 HashMap을 사용하였다. 투 포인터를 활용하는 곳은 HashMap의 size 즉 현재 구매한 보석의 종류들이 HashSet의 크기, 즉 진..
투 포인터 활용 - BOJ 2470 두 용액
2023. 3. 19. 21:15
Algorithm/Two Pointer
문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 접근 두 수의 합이 0에 가장 가까워야 한다. 하지만 데이터가 음수와 양수로 나뉘어져 있기 때문에, 두 수의 합의 절댓값을 가지고 판단해야 한다. 데이터 값이 중구난방으로 되어있어 바로 처리하기가 곤란하다. 정렬을 해서 음수 파트와 양수 파트를 나누고 양 끝에서 두 개의 포인터를 사용하여 투 포인터 전략을 사용해야 한다. 두 수의 합의 절댓값을 계산한 ..