돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/2544 (P1) 문제 태그 더보기 이분 매칭, 파라메트릭 서치 문제 풀이 맨처음에 이 문제를 볼 때는 DP가 생각났다. 상태를 잘 정의해서 풀면 $O(N^3)$에 문제를 해결할 수 있을 것 처럼 보였다. 하지만 다음 상태로 넘어가는 그 관계에 대해서 정의를 하는 것이 힘들어서 다른 방법을 찾았다. 위의 과정에서 생각을 하면서 이 문제를 좀 그리디하게 접근할 수 있다는 것을 깨달았다. 당연히 가장 높은 수를 없애는 방향으로 줄을 지워야 한다. 결국 가장 높은 수부터 k개의 줄을 이용해 어느 수 까지 없앨 수 있는 지를 알아야 한다. 가능한 최소(최대) 를 구하는 문제가 나온 이상, 결정론적으로 문제를 바꿔서 생각을 안해볼 수가 없다...

이분 매칭이란? 그래프중 특수한 그래프인 이분 그래프에서 두 그룹간의 최대 매칭을 의미한다. 이때 이분그래프는 전체 그래프에서 점 들을 두 그룹으로 나누었을 때, 같은 그룹내에는 간선이 존재하지 않게 나눌 수 있는 그래프를 의미한다. 보통 나눌 수 있는 경우가 여러가지기도 하지만, 문제에서 명확히 두 그룹을 분류해주는 경우가 많다. 예를 들어 왼쪽과 같은 이분그래프가 있다면 오른쪽 그림과 같이 3개의 매칭을 시켜 줄 수 있으므로 이분매칭의 값은 3이라고 할 수 있다. 그러면 어떠한 방식과 알고리즘으로 3이라는 값을 뽑아낼까? 호프크로프트라는 시간복잡도 $O(V\sqrt{E})$ 가 있지만 일단은 $O(VE)$알고리즘을 소개하려고 한다. $O(VE)$ 알고리즘 이 알고리즘은 기본적으로 완전 탐색과 같은 느..