네트워크 유량(Network Flow)은 네트워크 플로우라고도 불리며 이를 설명하기 전,유량 그래프(Flow Graph)에 대해서 먼저 알아봅시다.유량 그래프란 각 간선에 용량이라는 추가 속성이 존재하는 방향 그래프로각 간선은 유량을 흘려보낼 수 있는 파이프 역할을 합니다.이 그래프에서는 소스(Source)와 싱크(sink)가 존재하며소스는 유량이 시작되는 정점, 싱크는 유량이 도착하는 정점을 뜻합니다.유량 그래프에서는 아래와 같은 3가지의 속성을 만족합니다. 1. 용량 제한 속성 : 각 간선의 유량은 해당 간선의 용량을 초과할 수 없다.2. 유량의 대칭성 : u에서 에서 v로 유량이 들어올 경우 v입장에서는 u로 음수의 유량을 보내는 것과 같다.3. 유량의 보존 : 소스와 싱크를 제외하고 각 정점에 들..
플로이드 와샬(Floyd Warshall)은 간선에 비용이 있는 그래프에서모든 점에서 모든 점까지의 최단거리를 구할 수 있는 모든 쌍 최단거리 알고리즘입니다.이 알고리즘은 반복적 동적 계획법과 슬라이딩 윈도우 기법을 사용하며dist[i][j]는 i 정점에서 j 정점까지의 최단거리를 뜻할 때거치는 점(k) - 출발점(i) - 도착점(j) 순의 3중 포문을 이용하여매 k마다 모든 i, j값을 순회하여 k 정점을 추가적으로 경유하였을 때의 값이 더 작은 경우(dist[i][j] > dist[i][k] + dist[k][j])dist[i][j]값을 갱신하여 최단거리를 저장합니다.3중 포문의 형태를 띄고 있으므로 시간복잡도는 정점 개수가 V일 때 O(V^3)이 되며코드가 매우 간결하므로 V가 크지 않을 경우의 최..
벨만 포드(Bellman Ford)는 간선에 비용이 있는 그래프에서시작점부터 다른 정점까지의 최단거리를 구할 수 있는 단일 시작점 최단거리 알고리즘입니다.이는 다익스트라 알고리즘과 동일하지만 간선의 비용이 음수일 때도 사용할 수 있습니다.벨만 포드 알고리즘은 다익스트라와 동일하게 dist배열을 사용하며 dist[i]는 시작점에서 i번 정점까지의 최단거리를 뜻합니다.시작점의 dist값은 0, 나머지 모든 정점은 무한대로 초기화 한 뒤 dist배열을 갱신하는 작업을 진행하는데최단 거리는 정점 개수가 V일 때 최대 V-1개의 간선을 거쳐야 한다는 원리를 이용하여V-1번의 루프를 돌며 k번째 루프에서는 시작점으로부터 k개의 간선을 거쳐 도달할 수 있는 최단 경로를 dist에 저장합니다.이 때 최단 거리가 V개 ..
다익스트라(Dijkstra)는 간선에 비용이 있는 그래프에서시작점부터 다른 정점까지의 최단거리를 구할 수 있는 단일 시작점 최단거리 알고리즘입니다.이 때 간선의 비용이 음수가 아닐 경우에만 가능하며 간선의 비용이 음수일 경우 추후 배울 벨만 포드 알고리즘을 사용합니다.다익스트라 알고리즘은 dist배열을 사용하며, dist[i]는 시작점에서 i번 정점까지의 최단거리를 뜻합니다.시작점의 dist값은 0, 나머지 모든 정점은 무한대로 초기화한 뒤 시작점을 방문하는 것을 시작으로,아직 방문하지 않은 정점들 중 시작점으로부터 가장 거리가 작은 정점(u)을 방문한 뒤해당 정점(u)을 거쳐서 인접한 정점(v)으로 가는 거리(cost)가 dist에 있는 값보다 더 작을 경우(dist[v] > dist[u] + cost..
최소 스패닝 트리(Minimum Spanning Tree)는 무향그래프(Undirected Graph)에서간선마다 비용이 주어질 때 그 간선들의 비용의 합이 최소인 스패닝 트리입니다.이 때 여기서 스패닝 트리는 그래프의 정점 전부와 간선의 부분 집합으로구성된 부분 그래프 중 간선들이 사이클을 이루지 않는 트리를 말합니다. 그러므로 V개의 정점을 가지고 있는 그래프의 스패닝 트리는 모든 정점이 연결되어 있고정확히 V-1개의 간선으로 연결되어 있어야 합니다.이를 구하는 두가지 알고리즘이 있으며 아래와 같습니다. 1. 크루스칼 알고리즘2. 프림 알고리즘 두 알고리즘은 모두 각 단계마다 지금 가장 좋은 방법인 비용이 최소로 드는 방법으로 이동하는앞서 배운 탐욕법을 사용하여 최소 스패닝 트리를 구하게 됩니다.크루..
2-SAT(2-Satisfiability Problem)는 충족 가능성 문제 중 하나이며논리식을 논리곱 정규형으로 표현 했을 때 각 절에 두 개의 변수만이 존재하는 경우이 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제입니다.k-SAT는 NP-완전이라는 것이 증명되었으나 2-SAT문제 만이 다항 시간내에 풀 수 있습니다.논리곱 정규형으로 표현 된 절 중 하나인 (A∨B) 라는 절이 참이 되려면A가 거짓이라면 B는 무조건 참이여야 하며, B가 거짓이라면 A는 무조건 참이여야 합니다.이를 이용하여 ¬A → B 와 ¬B → A이라는 명제로 표현 될 수 있으며모든 절을 합하여 하나의 유향그래프를 생성할 수 있습니다.이제 이 그래프로 논리식이 참이 되는 변수값이 존재하는지 찾아야 하는데 조건은 아래와 같습니다..
SCC(Strongly Connected Component)는 강한 연결 요소이라고도 불리며유향그래프 상에서 두 정점 u와 v에 대해 양방향으로 가는 경로가 모두 있을 때 같은 SCC에 있다고 표현합니다.그래프를 SCC로 분리하는 방법으로는 타잔의 알고리즘을 사용합니다.이 알고리즘은 정점을 담는 하나의 스택과 한 번의 DFS만을 이용하여 분리하는데원리는 앞서 배운 간선 분류를 이용하여 아래와 같이 설명할 수 있습니다. u의 자손 v에 대하여 v를 루트로 하는 서브트리에서 v보다 먼저 발견된 정점으로 가는 역방향 간선이 있을 때,v보다 먼저 발견되었으면서 아직 SCC로 묶여있지 않은 정점으로 가는 교차 간선이 있다면 간선 (u, v)를 끊어서는 안된다. 이는 절단점 확인 알고리즘과 일정 부분 유사하며 추가..
절단점(Articulation Point) 또는 단절점이라고도 불리며무향그래프(Undirected Graph)에서 정점 하나를 삭제 했을 때 해당 정점이 포함된 그래프가두 개 이상의 컴포넌트(component)로 분리되는 정점을 말합니다.해당 정점이 절단점인지 확인하는 방법으로는 간단하게그 정점의 자손들이 모두 선조로 가지 않는다면 그 점은 절단점입니다.DFS를 이용하여 이를 좀 더 쉽게 구현합니다.정점의 발견 순서를 기록 한 뒤 이 노드에서 갈 수 있는 가장 작은 정점의 번호를 반환하는 함수를 만들어서한 정점의 자손들의 반환 값이 모두 이 정점의 발견 순서보다 크다면이 정점의 선조로 가지 않는다는 의미이므로 이 정점은 절단점입니다.이 때 루트 노드의 경우 이전에 발견한 노드가 없기에 절단점이 아니게 되..
간선 분류는 그래프의 모든 간선을 특징에 따라 4가지의 종류로 분류하는 작업입니다.4가지 종류는 아래와 같습니다. 1. 트리 간선 : 스패닝 트리에 포함된 간선2. 순방향 간선 : 스패닝 트리의 선조에서 자손으로 연결되나 트리 간선이 아닌 간선3. 역방향 간선 : 스패닝 트리의 자손에서 선조로 연결되는 간선4. 교차 간선 : 위 분류를 제외한 나머지 간선 여기서의 스패닝 트리는 모든 정점을 포함하며, 사이클이 존재하지 않는 트리의 특성도 만족하는 부분 그래프를 뜻합니다.(스패닝 트리에 대한 더 자세한 설명은 최소 스패닝 트리에서 진행합니다.)단 한번의 DFS를 통해 스패닝 트리를 따라가면서 조건에 맞게 간선을 분류합니다.이는 추후 그래프를 SCC로 분리하기 위해 사용하는 타잔의 알고리즘을 이해하는 데 도..
위상정렬(Topological Sort)은 의존성이 있는 작업들이 주어질 때이들을 어떤 순서로 수행해야 하는 지를 순서대로 나열하는 것을 의미합니다.사용법의 예로 대학의 선수과목 구조에서 특정 수강과목에 선수과목이 있다면 선수과목을 먼저 수강해야 하므로선후관계가 있는 이 구조를 그래프로 만들어 위상정렬하게 된다면 올바른 수강 순서를 찾을 수 있습니다.위상정렬이 가능하려면 유향그래프(Directed Graph)에 순환(cycle)이 존재하지 않아야하며이는 DAG(Directed Acylic Graph)여야 한다는 것을 알 수 있습니다.위상정렬은 아래의 2가지 방법을 사용하여 구할 수 있습니다. 1. DFS의 종료하는 순서를 기록한 뒤 뒤집는다.2. 들어오는 간선이 없는 정점을 큐에 넣은 뒤 큐에서 하나를 ..