Algorithm/H. Trees & Graphs (33) 썸네일형 리스트형 152. Stable Marriage Problem 안정적인 결혼 문제(Stable Marriage Problem, SMP)는 크기가 동일한 두 집합에서 안정적인 매칭(Stable Matching)을 찾는 문제이다. 두 집합 간의 안정적인 매칭이라는 것은 다음과 같다. 각 집합의 원소는 상대 집합의 원소들에 대한 서로 다른 선호도를 가진다. 첫 번째 집합과 두 번째 집합의 원소가 일대일로 매칭되어 있다. 첫 번째 집합에 속한 원소 $A$, $B$가 두 번째 집합에 속한 원소 $C$, $D$와 각각 매칭되어 있을 때 $A$가 $C$보다 $D$를 선호하면서 $D$가 $B$보다 $A$를 선호하는 경우는 존재하지 않는다. 세 번째 조건을 다시 설명하면 서로 매칭되지 않은 두 원소 모두가 상대 원소를 자신과 매칭된 원소보다 더 선호하는 경우가 존재하지 않는다는 것.. 141. Bipartite Matching 플로우 문제를 풀다 보면 특수한 형태의 그래프가 자주 등장하는 것을 알 수 있다. 아래의 그래프를 보자. 소스에서 첫 번째 그룹의 정점들로 가는 간선들이 있고, 첫 번째 그룹의 정점들에서 두 번째 그룹의 정점들로 가는 간선이 있고, 두 번째 그룹의 정점들에서 싱크로 가는 간선이 있다. 각 간선의 용량은 전부 $1$이다. 위 그래프에서 소스와 싱크를 없애고 간선의 방향 표시도 없애면 아래와 같은 이분 그래프가 된다. 간선의 용량이 전부 $1$이므로, 이 그래프에서 최대 유량을 구하는 문제는 첫 번째 그룹에 속하는 정점들과 두 번째 그룹에 속하는 정점들 간의 최대 매칭(Maximum Matching)의 크기를 찾는 문제로 생각할 수 있다. 앞서 소스와 싱크에 연결된 간선들의 용량도 전부 $1$이었으므로 각각.. 140. Edmonds-Karp Algorithm 다음과 같은 그래프에서 포드-풀커슨 알고리즘으로 최대 유량을 구하는 경우를 생각해 보자. 포드-풀커슨 알고리즘은 증가 경로를 정하는 방법을 정의하지 않으므로, 운이 좋으면 증가 경로 $\text{S}$ - $\text{A}$ - $\text{T}$로 $10000$의 유량을 보내고 증가 경로 $\text{S}$ - $\text{B}$ - $\text{T}$로 $10000$의 유량을 보내서 두 번의 탐색으로 $20000$의 유량을 보낼 수 있다. 하지만 이 그래프에는 $\text{S}$ - $\text{A}$ - $\text{B}$ - $\text{T}$라는 증가 경로가 존재한다. 만약 이 경로를 선택할 경우 보낼 수 있는 유량은 $1$이고, 그러면 간선들의 유량은 다음과 같이 변한다. 이제 $\text{S.. 139. Ford-Fulkerson Algorithm 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)은 일반적인 방향 그래프에서 최대 유량을 구하는 가장 간단한 알고리즘이다. 최대 유량은 일반적으로 소스에서 간선들을 따라서 싱크로 흘려보낼 수 있는 유량의 최댓값을 의미한다. 이 알고리즘은 다음과 같은 방법으로 작동한다. 1. 모든 간선의 유량을 $0$으로 초기화한다. 2. 소스에서 싱크로 데이터를 보낼 수 있는 경로를 찾는다. 이 경로를 증가 경로(Augmenting Path)라고 한다. 3. 증가 경로 중 더 보낼 수 있는 데이터의 양이 가장 작은 간선을 찾는다. 이 간선에 더 보낼 수 있는 데이터의 양을 $w$라고 하자. 4. 찾은 증가 경로를 통해 $w$의 데이터를 보낸다. 증가 경로에 포함된 모든 간선의 유량이 $w$만큼 증가하고.. 138. Network Flow 네트워크 플로우(Network Flow)는 그래프 상의 두 정점 사이에 데이터를 얼마나 많이 흘려보낼 수 있는지를 구하는 분야이다. 일반적으로 네트워크를 생략하고 그냥 플로우라고 부르는 경우가 많다. 이제부터 앞에서 간단하게 소개하고 넘어갔던 간선의 용량이 중요하게 다뤄진다. 플로우에서 나오는 용어들의 정의와 특징은 다음과 같다. 정점 $u$에서 정점 $v$로 가는 방향 간선이 존재하고 이 간선의 용량이 $w$일 때, 최대 $w$만큼의 데이터가 이 간선을 따라 정점 $u$에서 정점 $v$로 이동할 수 있다. 정점 $u$에서 정점 $v$로 가는 간선을 통해 이동하는 데이터의 양이 $k$일 때, $k$를 이 간선의 유량(Flow)이라고 한다. 간선의 유량은 간선의 용량을 넘을 수 없다. 데이터를 처음으로 흘.. 133. 2-SAT 충족 가능성 문제(SAT, Satisfiability Problem)는 Boolean 변수들(True 또는 False 중 한 가지 값을 가질 수 있음)로 이루어진 식의 값이 True가 되게 하는 변수들의 값 조합이 존재하는지를 알아내는 문제이다. 이러한 식은 불 연산식(Boolean Expression)이라고 부르며 다음과 같은 두 가지의 형태로 나타낼 수 있다. 식에서 $\neg$, $\wedge$, $\vee$ 기호는 각각 NOT, AND, OR 연산자와 같은 의미를 가지며 $\neg$ 연산자의 우선순위가 가장 높다. CNF(Conjunctive Normal Form): $f = (x_1 \vee x_2) \wedge (\neg x_3 \vee x_1 \vee x_4) \wedge (\neg x_2 .. 132. Tarjan's Algorithm 타잔 알고리즘(Tarjan's Algorithm)은 그래프의 SCC를 전부 구하는 또 다른 알고리즘으로, 다음과 같은 방법으로 작동한다. 1. 아직 방문하지 않은 정점 하나를 골라 그 정점에서 DFS를 실행한다. 2. 새로운 정점을 방문할 때마다 그 정점의 방문 순서를 저장한다. 이를 우선순위(값이 작을수록 높음)로 간주하고, 정점마다 그 정점에서 도달할 수 있는 정점들의 우선순위 값 중 가장 높은 것을 저장한다. 이때 이미 SCC로 묶인 정점의 우선순위는 무시한다. 3. 어떤 정점의 DFS가 종료될 때, 그 정점에서 도달할 수 있는 정점들 중 우선순위가 가장 높은 정점이 자신일 경우 스택에 쌓인 정점을 자신이 나올 때까지 전부 뽑고, 그 정점들을 하나의 SCC로 묶는다. 4. 모든 정점이 SCC로 묶일.. 131. Kosaraju's Algorithm 먼저 임의의 정점 $v$가 주어졌을 때 $v$를 포함하는 SCC 하나를 구하는 방법을 살펴본다. $v$에서 이동할 수 있는 정점들과 $v$로 이동할 수 있는 정점들의 교집합을 구하면 그 집합에 속한 정점들이 한 SCC로 묶이게 된다. $v$에서 이동할 수 있는 정점들은 DFS로 쉽게 구할 수 있고, $v$로 이동할 수 있는 정점들은 간선들을 전부 뒤집은 다음 DFS를 실행하면 구할 수 있다. 두 번의 DFS에서 모두 방문한 정점들은 $v$와 같은 SCC에 속한다. 따라서 다음과 같은 방법으로 그래프의 SCC를 전부 구할 수 있다. (그래프에 존재하는 정점의 수가 $n$이라고 가정한다.) 1. 아직 SCC로 묶이지 않은 정점 중 하나를 선택해서 그 정점에서 DFS를 실행한다. 2. 그래프의 간선을 전부 뒤.. 이전 1 2 3 4 5 다음
