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 다음과 같은 그래프에서 포드-풀커슨 알고리즘으로 최대 유량을 구하는 경우를 생각해 보자. 포드-풀커슨 알고리즘은 증가 경로를 정하는 방법을 정의하지 않으므로, 운이 좋으면 증가 경로 S - A - T로 10000의 유량을 보내고 증가 경로 S - B - T로 10000의 유량을 보내서 두 번의 탐색으로 20000의 유량을 보낼 수 있다. 하지만 이 그래프에는 S - A - B - 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)이라고 부르며 다음과 같은 두 가지의 형태로 나타낼 수 있다. 식에서 ¬, ∧, ∨ 기호는 각각 NOT, AND, OR 연산자와 같은 의미를 가지며 ¬ 연산자의 우선순위가 가장 높다.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. 모든.. 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 다음 목록 더보기
