graph
[Algorithm] 플로이드-워셜(Floyd-Warshall)
[Algorithm] 플로이드-워셜(Floyd-Warshall)
2023.03.12플로이드-워셜(Floyd-Warshall)? 플로이드-워셜은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이며 다익스트라보다 구현이 쉽다. 플로이드-워셜은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야하기 때문에 2차원 배열에 최단 거리 정보를 저장한다. 또한, DP의 특징을 가지고 있어서 노드의 개수(N)번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신해나간다. 구현 설명 플로이드-워셜은 임의의 노드 s에서 e까지 가는데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와..
[Baekjoon] 1167: 트리의 지름
[Baekjoon] 1167: 트리의 지름
2023.03.08문제 트리에서 두 점 사이의 거리가 가장 긴 길이를 트리의 지름이라 하는데 트리의 지름을 구하는 문제이다 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q1167 { private static List tree; private static boolean[] visited; private static int maxVertex; private static int max; public static void main(String[] args) throws IOException { BufferedReader br = new..
[Algorithm] 위상 정렬(Topological Sort)
[Algorithm] 위상 정렬(Topological Sort)
2023.03.07위상 정렬(Topological Sort)? 위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘으로, 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것이다. 실생활을 예로 들면, 인터넷 검색을 하기 위해선 다음과 같은 순서로 행동해야한다. 컴퓨터 전원 키기 -> 브라우저 키기 -> 검색 엔진 포털 진입 -> 검색 위 순서가 바뀐다면 검색을 할 수 없을 것이다. 위상 정렬은 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 된다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능하다. 여기서 주의할 점은 E가 수행되기 위해선 B와 D가 모두 수행되어야 한다는 점이다. 비순환 방향 그래프 (DAG: Di..
[Algorithm] 다익스트라(Dijkstra)
[Algorithm] 다익스트라(Dijkstra)
2023.02.26다익스트라(Dijkstra)? 다익스트라(Dijkstra) 알고리즘은 에츠허르 다익스트라가 고안한 알고리즘으로, 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 대표적인 최단 경로 알고리즘이다. 특징 그래프 방향의 유무는 상관 없으나, 간선들 중 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다. 음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용할 수 있다. 또한 그래프 내에 가중치 합이 음인 사이클이 존재한다면 무한히 음의 사이클을 도는 경우 경로 합이 음수 무한대로 발산하기 때문에 그래프 내의 최단 경로는 구성할 수 없다. 구현 P[A][B]는 A와 B사이의 거리라고 가정한다. 출발점으로부터 최단거리를..
[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm)
[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm)
2023.02.19크루스칼 알고리즘 (Kruskal Algorithm)? 크루스칼 알고리즘은 그래프 내의 모든 간선의 가중치를 확인하고 가장 작은 가중치부터 확인해서 최소 신장 트리를 만드는 알고리즘으로, 탐욕적인(greedy) 방법을 통해 구현할 수 있다. greedy? 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다. 크루스칼 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. 구현 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. 가장 낮은 가중치를 먼저 선택한다. 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의..
[Algorithm] 백트래킹(BackTracking)
[Algorithm] 백트래킹(BackTracking)
2023.02.14백트래킹? 백트래킹은 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다. 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(DFS)과 너비우선탐색(BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS는 큐의 크기가 매우 커질 수 있고 속도도 차이가 없기 때문에 경우의 수 구하기는 일반적으로 DFS가 편리하다. 출처: 나무위키 DFS & 백트래킹 백트래킹은 DFS를 사..