코학다식

문제 링크 :: https://www.acmicpc.net/problem/11375 Solution 이분 매칭으로 쉽게 풀 수 있는 문제이다. M개의 일을 해야 하는 상황에서 N명의 직원들 각각이 할 수 있는 일이 정해져 있고, 직원들은 하나의 일만 담당할 수 있다. 이분 매칭 알고리즘 설명 글에서 이분 매칭은 이분 그래프에서 한 그룹의 정점에서 다른 그룹의 정점으로 간선을 연결할 때 하나의 간선으로만 연결되는 것을 의미한다고 했다. 일과 직원은 서로 같은 그룹끼리는 연결되지 않으면서 다른 그룹끼리만 연결 가능한, 전형적인 이분 그래프라고 할 수 있다. 이 문제는 이분 매칭을 최대한 많이 가능하게 만드는 것을 요구하고 있다. 그렇다면 어떻게 해야 이분 매칭을 최대한 많이 할 수 있을까? 이것 역시 이분 ..

최근 배우게 된 알고리즘 중 가장 실생활과 밀접한 관련이 있다고 느껴지는 알고리즘이다. (이미 내가 사용하고 있을 수도 있지만) 이름을 알고 있는 알고리즘이 아직 그다지 많지 않은데, 열심히 공부해서 얼른 수를 늘리고 싶다. 문제를 해결할 때 필요한 알고리즘을 적재적소에 떠올리고 싶은데 지식이 부족하다. 그래도 과거의 나보단 낫다는 것에 항상 의의를 두려고 노력 중. 이분 매칭(Bipartite Matching) 이분 매칭은 네크워크 플로우(Network flow)에서 등장하는 개념 중 하나이다. 그렇지만 네트워크 플로우를 처음 들어 본다고 하더라도 쉽게 이해할 수 있다. 이분 매칭은 이분 그래프에서 한 그룹의 정점에서 다른 그룹의 정점으로 간선을 연결할 때 각각이 일대일 대응으로 매칭되는 것을 의미한다..