재원블로그 재원블로그

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

위상 정렬은 순서가 정해진 일들에 대해서 그 순서를 위배하지 않고 일들의 처리 순서를 만드는 방법을 만드는 알고리즘이다. 대표적으로 선수 과목을 예로 들 수 있다. 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 + ..

투 포인터는 말 그대로 두 개의 포인터를 사용하여 탐색을 수행하는 알고리즘이다. 어떤 특정한 조건을 만족하는 쌍을 구하고자 할 경우, 단순 이중 루프를 이용하여 계산하면 O(N^2) 시간이 걸리는데, 이는 입력값 N이 100000만 넘어가게 되도 100억번을 수행해야 하므로 굉장히 느리다. 이 때 투 포인터 기법을 사용하면 O(N) 시간에 가능하게 된다. 투 포인터의 경우 보통 두 가지 경우로 사용할 수 있는데, 한 가지는 한 포인터는 배열의 맨 앞에, 다른 포인터는 배열의 맨 뒤에 위치하고 조건에 따라 점점 중간으로 가는 방식이고, 다른 한 가지는 앞이나 뒤에서 동시에 출발하여 다른 끝까지 도달하는 방식이다. 위 그림의 경우 첫번째 방식인데, 이 때 배열이 반드시 정렬되어 있어야 한다. 보통 오름차순으..