네트워크 플로우 (Network Flow) - 에드몬드 카프 알고리즘 (Edmonds-Karp) 네트워크 플로우(Network Flow)는 한 정점에서 다른 정점까지 흐를 수 있는 데이터의 최대 크기가 어느 정도인지를 확인하는 알고리즘입니다. 유향 그래프에서 각 간선은 데이터가 흐를 수 있는 정해진 용량으로 제한되어 있으며 이를 최대한의 양으로 얼마나 흐르게 할 수 있는 지를 확인합니다. 이것을 최대 유량 문제(Max Flow)로 정의하며 해결하기 위한 알고리즘으로 에드몬드 카프 알고리즘(Edmonds-Karp)을 적용합니다. 또한 네트워크 플로우는 도로망의 교통 흐름을 분석하거나 전자 회로의 전류, 배수관을 흐르는 유체, 유량 등을 연구하는데 적용됩니다. 현재 흐르고 있는 데이터의 양을 유량, 간선에 ..

강한 연결 요소 (Strongly Connected Component) 방향성이 존재하는 유향 그래프에서 모든 정점이 다른 모든 정점들에 대하여 방문할 수 있는 경우 즉, 어떤 두 정점 간의 경로가 존재하면 그 집단이 강하게 연결되었다고 표현합니다. 이것을 강한 연결 요소 혹은 강한 결합 요소라고 말합니다. 또한 전체 그래프가 강한 연결 요소가 아니더라도 전체 그래프의 부분 그래프 안의 정점들이 강한 연결 요소로 묶여있다면 그 부분 그래프는 강한 연결 요소가 됩니다. 이것으로 볼 때, 강한 연결 요소가 성립하는 그래프는 반드시 하나의 유향 사이클을 포함하는 그래프입니다. 알고리즘 원리 깊이 우선 탐색(DFS)을 기반으로 하는 선형 탐색 알고리즘을 사용할 수 있습니다. 코사라주의 알고리즘과 타잔의 알고리즘..

위상 정렬 알고리즘 (Topology Sort) 위상 정렬은 방향성이 있는 유향 그래프에서 순서가 정해져있는 정점들의 순서를 거스르지 않으면서 모든 정점을 나열하는 알고리즘입니다. 위상 정렬의 대표적인 예시는 다음과 같습니다. 예를 들어 컴퓨터공학과에서 알고리즘 과목을 수강하고자 할 때 해당 과목을 수강하기 위한 선수 과목들이 존재합니다. 즉, 알고리즘을 수강하기 위해선 자료구조를 먼저 수강해야 하며 C프로그래밍을 수강하기 위해서는 먼저 이산수학을 수강해야 할 것입니다. 순서가 존재하는 유향그래프에서 위 예시를 위상 정렬하면 다음과 같은 순서가 나타납니다. 이산수학 -> 프로그래밍 원리 -> C프로그래밍 -> 자료구조 -> 알고리즘 위상 정렬을 통해 올바른 수강순서를 찾아낼 수 있습니다. 이처럼 선후 관..

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘은 그래프에서 모든 정점 간의 최단 거리를 구하는 알고리즘입니다. 데이크스트라 알고리즘이 하나의 정점(시작 정점)으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이었다면, 플로이드-워셜 알고리즘은 모든 정점에서 모든 정점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘이며 음의 경로가 존재하는 그래프에서도 사용할 수 있습니다. 또한 플로이드-워셜 알고리즘은 다이나믹 프로그래밍 기법이 적용될 수 있습니다. 알고리즘 원리 플로이드-워셜 알고리즘은 정점 A에서 정점 C에 대한 최단경로를 구하기 위해 `정점 A에서 정점 C에 대한 경로`와 `정점 A에서 정점 B를 거쳐 정점 B에서 정점 C로 가는 경로`를 ..

데이크스트라 알고리즘 (Dijkstra Algorithm) 데이크스트라 알고리즘은 그래프에서 정점 간의 최단 경로를 찾는 탐색 알고리즘입니다. 예를 들어 여러 개의 도시가 있을 때 도시 사이를 연결하는 도로의 길이를 최소 비용으로 계산하여 건설하고자 할 때와 같이 현실 세계의 다양한 상황에서 사용될 수 있는 알고리즘입니다. 또한 그래프 내에서 하나의 최단 경로는 다른 여러 최단 경로로 만들어질 수 있으므로 기존에 저장되었던 최단 경로의 결괏값이 그대로 사용될 수 있다는 점에서 다이나믹 프로그래밍을 적용하여 사용할 수 있습니다. 알고리즘 원리 위 그림에서 정점 1로부터 정점 2, 3, 4로의 최단 경로가 각각 5, 9, 13으로 설정되어 있습니다. 정점 1은 방문이 완료되었으므로 다음으로 가장 가까운 정점..

에라토스테네스의 체 (Sieve of Eratosthenes) 소수는 1보다 큰 자연수 중 1과 자기자신만을 약수로 가지는 수입니다. 특정한 자연수가 소수인지 아닌지는 다음과 같은 간단한 알고리즘을 통해 판별할 수 있습니다. // 소수 판별 O(N^(1/2)) #include using namespace std; bool isPrime(int x) { int rt = (int)sqrt(x); for (int i = 2; i > x; cout