Hani_Levenshtein

이번 포스팅의 주제인 이분 매칭 문제는 네트워크 플로우 연장선에 있는 문제입니다. 2020/09/09 - [알고리즘] - 포드 풀커슨 알고리즘 우선, 이분 매칭을 공부하기 위해선 이분 그래프라는 것을 알 필요가 있습니다. 이분 그래프란 두 집합으로 나뉜 그래프의 정점들의 간선이 상대 집합에 속한 정점으로 연결된 그래프입니다. 성별이나, 주종관계, 사람과 작업 등의 관계가 주어진다면 이를 이분 그래프로 표현할 수 있습니다. 여기서 이분 그래프의 각 요소들을 문제의 조건에 맞춰 대응시키는 것이 이분 매칭 문제입니다. 이런 이분 매칭 문제는 앞서 소개한 네트워크 플로우를 이용하면 쉽게 풀 수 있습니다. 이분 그래프의 각 간선을, 연결되지 않은 것(0) 과 연결된 것(1) 인 용량이 1인 간선으로 고려할 수 있..