문제 링크

• http://icpc.me/13974

문제 링크

• http://icpc.me/11066

수정 예정

monotone stack은 몇몇 문제들의 시간 복잡도를 O(n)정도로 줄어주는 강력한 테크닉입니다.

최악의 경우

이전 글 마지막 부분을 다시 가져와봅시다.

이번 글에서는 Union Find를 구현해봅시다. 배열을 이용한 구현과 트리를 이용한 구현, 총 두 가지를 살펴보도록 하겠습니다.

Union Find란?

Union Find는 상호 배타적 집합(disjoint set)을 표현할 때 쓰는 자료구조입니다.
라고 설명을 하면 무슨 소리인지 잘 모를 수도 있겠죠.

아주 간단하게 설명하자면, 전체 집합을 공통원소가 없는 부분 집합들로 나눠서 저장하는 자료구조입니다.

이분 매칭이란?

이전 글에서 Max-Flow를 구하는 방법에 대해 알아보았고, 마지막 부분에서는 문제 하나를 풀어보았습니다.
icpc.me/11375 문제를 풀어보았고, 문제를 그래프로 모델링하면 아래 사진처럼 그래프가 만들어졌습니다.

작동 방식

네트워크 플로우 관련 알고리즘 중 가장 기초적인 Max-Flow 중, Ford-Fulkerson알고리즘에 대해 알아보도록 하겠습니다.
이 알고리즘은 Max-Flow 뿐만 아니라 네트워프 플로우 관련 알고리즘 중 가장 먼저 고안된 알고리즘입니다.
동작 원리는 매우 간단합니다. 유량 네트워크에 있는 모든 간선의 유량을 0으로 초기화 시킨 뒤, 소스에서 source에서 sink로 유량을 더 보낼 수 있는 경로를 찾아 흘리는 동작만 반복하면 됩니다.

플로우 알고리즘

이전까지 다룬 그래프 알고리즘에서는 간선에 거리, 가중치 등을 나타내는 cost라는 값이 있었습니다. 네트워크 플로우에는 capacity라는 개념이 추가됩니다.
네트워크 플로우는 네트워크 유량이라고 부르기도 합니다. 핵심이 되는 아이디어는 (u, v)를 연결하는 간선이 있을 때, u에서 v로 용량 이하의 유량을 보낼 수 있다는 것입니다.
네트워크 플로우 관련 알고리즘은 위에서 말한 핵심 아이디어를 기반으로 해서, 시작점(source)에서 도착점(sink)까지 시작점에서 유량을 흘려보내 도착점까지 보내는 것이 목표입니다. 최대한 많이 흘려보내 Max-Flow, 최소한의 비용을 들여서 최대한 많이 흘려보내는 Min-Cost Max-Flow 등 여러 알고리즘이 있고, 몇 개의 글을 통해 하나씩 소개하려고 합니다.