재원블로그 재원블로그

유향 그래프에서 모든 정점이 도달 가능하면 강하게 연결되었다고 한다. 여기서 강한 연결 요소는 부분 그래프의 모든 정점이 강하게 연결된 것이다. 강한 연결 요소를 찾는 것은 O(V + E) 시간에 가능하다. Transpose graph가 이를 찾는 알고리즘에서 사용되는데, 이는 원래 그래프의 모든 간선의 방향이 반대인 그래프이다. 강한 연결 요소를 찾는 알고리즘은 다음과 같다. 1. DFS를 수행한다. 2. DFS를 수행하고 각각이 끝날 때마다 스택에 집어넣는다. 3. Transpose graph에 대해서 DFS를 수행한다. 이 때 시작점은 스택에서 pop하는 순서대로이다. 4. DFS가 끝날 때마다 저장한다. 이를 C++로 구현하면 다음과 같다. int v, e; vector edges[10001]; ..

유니온 파인드는 집합간의 합집합을 나타낼 때 사용하는 자료구조이다. A[] = { 0, 1, 2 }, B[] = { 1, 2, 3 } 이라고 하고, B 배열이 A 배열로 합쳐진다고 가정하면 union 연산을 수행한 후에는 A[] = { 0, 1, 2, 3 } 이 되는 것이다. 유니온 파인드에서는 두 가지의 연산을 수행할 수 있는데, 한 집합의 대표를 리턴하는 find 와 두 집합을 합치는 union 연산이 있다. 초기 상태에는 한 원소가 하나의 집합이 되고, 그 원소가 그 집합의 대표가 된다. C++로 구현한 기본적인 유니온 파인드는 다음과 같다. vector parent; void init(vector p) { for (int i = 0; i < parent.size(); i++) { parent[i]..

위상 정렬은 순서가 정해진 일들에 대해서 그 순서를 위배하지 않고 일들의 처리 순서를 만드는 방법을 만드는 알고리즘이다. 대표적으로 선수 과목을 예로 들 수 있다. C 과목을 들으려면 B를 들어야 하고, B 과목을 들으려면 A 과목을 들어야 한다고 하자. 그러면 수강 순서는 A -> B -> C 가 될 것이다. 이 순서를 만드는 것이 위상 정렬이다. 위상 정렬은 DAG (Directed Acyclic Graph) 에서만 성립한다. 즉, 유향 그래프여야 하며, 사이클이 없어야 한다. 무향 그래프의 경우 A -> B 와 B -> A 가 모두 가능하여 선수 과목이라는 조건에 모순이다. 또한 C를 듣기 위해서 B를 듣고, B를 듣기 위해서는 A를 듣는데, 이 때 A를 듣기 위해서 C를 들어야 한다면 이 또한 모..

이진 탐색은 정렬되어 있는 요소들에게만 사용할 수 있다. 일반적인 순차 탐색으로는 O(N)의 시간이 소요되지만, 이진 탐색을 사용하면 O(log N) 시간이 소요된다. C++로 구현한 기본적인 구현은 다음과 같다. int binarySearch(int key) { int low = 0; int high = MAX - 1; while (low arr[mid]) { low = mid + 1; } else if (key < arr[mid]) { high = mid - 1; } else { return mid; } } return -1; } 이 코드는 key가 정해진 배열에 존재하는지 여부를 판단할 수 있고, 만약 있다면 그 인덱스를 리턴하고, 없다면 -1을 리턴한다. 배열에서 key의 존재 유무를 판단하는 것..

대표적인 최단 경로 알고리즘 중에서 3번째 플로이드 워셜 알고리즘이다. 플로이드 워셜 알고리즘은 다익스트라나 벨만-포드와 다르게 1:N이 아닌 N:N 의 최단 시간을 찾을 수 있다. 최악 시간 복잡도는 O(|V|^3) 이다. 플로이드 워셜 알고리즘은 처음에 간선들의 정보와 자기 자신으로의 경로는 0이라는 정보만 주고, 모든 정점들의 경유를 하나씩 열면서 직접 가는 것보다 경유하는게 더 짧은지를 확인한다. 플로이드 워셜은 음수 사이클이 없는 그래프에서 음수 가중치가 있어도 사용할 수 있다. C++로 구현한 코드는 다음과 같다. #define INF 1000000000 int n; vector edges; vector floyd_warshall() { vector dist(n + 1, vector(n + 1..

최단 경로를 구하는 두번째 알고리즘 벨만 포드 알고리즘이다. 이 알고리즘은 다익스트라와 마찬가지로 하나의 시작점에서 다른 정점들간의 최소 시간을 구하는 알고리즘이다. 최악 시간 복잡도는 O(|V||E|)이다. 여기서 |V|는 정점의 개수, |E|는 간선의 개수이다. 다익스트라는 최악 시간 복잡도가 O(|E| + |V| log|V|) 인데 이 알고리즘을 사용하는 이유는 음수 가중치에 대해서도 적용할 수 있기 때문이다. 또한 음수 사이클의 존재 유무까지 판단할 수 있다. 이 알고리즘은 다익스트라와 같이 BFS 기반의 연산을 하는 것이 아닌 플로이드 워셜 알고리즘같이 다중 반복을 통해 문제를 해결한다. 그래서 우선순위 큐를 사용하지 않는다. 이 알고리즘은 초기에 start의 dist가 0이라는 것 빼고 모든 ..

가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘에는 대표적으로 다익스트라, 벨만-포드, 플로이드-워셜이 있다. 그 중 다익스트라에 대해서 정리하는 글이다. 다익스트라 알고리즘은 우선순위 큐를 이용할 경우 O(E + VlogV)로 알려져 있다. 여기서 E는 간선의 개수이고, V는 정점의 개수이다. 이 알고리즘은 무향, 유향 상관없이 적용 가능하지만, 음의 가중치가 있으면 사용할 수 없다. 다익스트라 알고리즘은 하나의 시작 정점에서 다른 정점들과의 최단 시간을 알아낼 때, 즉 1 : N일 때 사용할 수 있다. 다익스트라 알고리즘을 C++로 구현한 코드는 다음과 같다. #define INF 1000000000 int v; vector edges; vector dijkstra(int start) { vect..

이진 탐색은 정렬된 배열에서 탐색 시간을 줄이기 위한 알고리즘이다. 배열 안에서 어떤 원소 E를 찾을 때, 단순 선형 탐색으로 구현할 경우 O(N) 시간이 걸린다. 하지만 이진 탐색을 수행하면 O(log N) 시간에 수행할 수 있다. 위 그림과 같이 크기가 7인 배열이 존재하고, 이 배열은 오름차순으로 정렬되어있다. 인덱스는 0부터 시작하여 6까지 존재하게 된다. 이진 탐색은 정렬된 배열의 가운데와 구해야 하는 원소를 비교하여 절반만큼 비교 범위를 줄여나가는 것이다. 위 그림에서 mid = (low + high) / 2 를 구하면, (0 + 6) / 2 = 3이고, 3번 인덱스의 값인 6과 비교하게 된다. 만약 구해야 하는 숫자 M = 7이라고 가정하자. 7은 mid보다 크므로, [low = mid + ..