천복 만복 만만복🎊

그래프가 주어졌을 때, 모든 정점에서 대해서 다른 정점으로의 최단 경로를 구하는 것을 All Pair Shortest Path 이라고 한다. All Pair Shortest Path 를 구하는 알고리즘에는 플로이드-워셜 알고리즘이 있다. 플로이드 워셜 알고리즘은 일종의 동적 계획법(Dynamic Programming) 의 원리를 이용해서 모든 정점 쌍의 최단경로를 구한다. 알고리즘에 쓰이는 점화식을 나타내면 다음과 같다. dp[k][i][j] = min{dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]}; dp[k][i][j] 는 (1, 2, … , k) 에 속한 정점만을 경유하여 정점 i에서 정점 j로까지 도달할때 최단길이를 의미한다. 이 때 정점 k를 경유하는..

SPFA(Shortest Path Faster Algorithm) 은 벨만포드 알고리즘을 개선한 알고리즘이다. v - 1번 반복하는 동안 매 반복마다 모든 간선에 대해서 간선 경감을 진행하는 대신, 간선 경감이 일어나는 정점에 대해서만 그 정점에 연결된 간선들에 대해서 다음 간선 경감을 진행하는 방식이다. 최악의 경우 O(V^3) 의 시간복잡도를 갖지만, 평균적으로 O(E) 의 시간복잡도를 갖는다. https://www.acmicpc.net/problem/11657 package 최단경로.spfa.타임머신; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.A..

그래프가 주어졌을 때, 한 노드에서부터 다른 모든 노드들까지의 최단 거리를 구하는 것을 Single Point Shortest Path 라고 한다. Single Point Shortest Path 를 구하는 알고리즘에는 벨만포드 알고리즘 과 다익스트라 알고리즘 이 있다. 벨만포드 알고리즘은 O(V^3) 시간복잡도를 갖는다. 이는 다익스트라보다 오래 걸리는 수치다. 그러나 그래프에서 음수 가중치가 존재할 때도 사용 가능하며, 음수 사이클이 있는지 판별할 수도 있다. 알고리즘의 기본원리는 이렇다. V개의 정점과 E개의 간선으로 이루어진 그래프에서 어떤 정점 A와 B 사이의 최단경로 상에 존재하는 간선의 개수는 최대 V - 1 개이다. 따라서 시작점의 distance를 0으로 설정하고 V - 1 번 반복하면서..

그래프가 주어졌을 때, 한 노드에서부터 다른 모든 노드들까지의 최단 거리를 구하는 것을 Single Point Shortest Path 라고 한다. Single Point Shortest Path 를 구하는 알고리즘에는 벨만포드 알고리즘 과 다익스트라 알고리즘 이 있다. 다익스트라 알고리즘은 우선순위 큐로 구현시 O(ElogE) 시간복잡도를 갖는다. 벨만포드 알고리즘 보다 더 빠르다. 구현 방식은 최단 거리 계산이 완료된 정점을 계속해서 추가하는 방식으로 BFS, 프림 알고리즘과 유사하다. https://www.acmicpc.net/problem/1753 package 최단경로.다익스트라.최단경로; import java.io.BufferedReader; import java.io.IOException; ..

위상정렬은 싸이클이 없는 방향그래프(DAG) 에서 그래프를 순회하는 방법 중 하나이다. 어떤 일을 먼저 해야 다른 일을 할 수 있는 (전후관계가 있는) 일들의 수행 순서와 같은 것들을 계산할 수 있다. BFS 와 상당히 유사한 방법으로 구현할 수 있다. https://www.acmicpc.net/problem/2252 package 위상정렬.줄세우기; // https://www.acmicpc.net/problem/2252 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import jav..

그래프가 주어졌을 때, 모든 정점과 간선의 일부만으로 구성한 트리를 스패닝 트리라고 한다. 이 중에서 간선 가중치의 총합이 가장 작은 트리를 최소 스패닝 트리(Minimum Spanning Tree) 라고 한다. MST를 구하는 알고리즘은 2가지가 있다. 프림 알고리즘과 크루스칼 알고리즘이다. 프림(Prim) 알고리즘 프림 알고리즘은 BFS 와 유사한 방식으로 진행되며, 최초 임의의 정점을 MST에 추가한 뒤, 아직 MST에 포함되지 않은 정점을 연결하는 간선 중 최소인 간선을 MST에 추가하는 방식이다. 우선순위 큐를 이용해서 구현하면 O(ElogE) 의 시간복잡도를 갖는다. https://www.acmicpc.net/problem/1922 package mst.프림.네트워크연결; import java..

private static void quickSort(int[] arr, int first, int last) { if (first > last) return; int i = first; int j = last; int mid = first + (last - first) / 2; swap(arr, first, mid); int pivot = first; while(i < j) { while(i arr[pivot]) j--; if (i < j) { swap(arr, i, j); } } swap(arr, pivot, j); quickSort(arr, first, j - 1); quickSort(arr, j + 1, last); } private static void swap(int[] arr, int i, ..