728x90 알고리즘/Network1 Bipartite matching 개요 Network flow, 비선형 그래프 이분 그래프의 최대유량 구하기 접근 이분 이분 이라는 단어를 보고 파블로프의 개마냥 이분탐색을 생각하기 쉽다. 이분과 매칭이라니, 리스트를 절반으로 나누면서 탐색하는 문제인가? 하는 생각을 하기 쉽다. 하지만 이분탐색과는 단 하나도 관련이 없다. 우선 그래프란, 컴퓨터가 데이터를 이해하고 인간이 데이터를 처리하기 쉽도록 만든 데이터의 연결관계이다. 이걸 자료구조라고 하고, 연결 방식에 따라 선형과 비선형으로 나뉘는데 그래프는 이 중 비선형 구조에 해당한다. 선형 구조는 리스트, 스택, 큐처럼 인접한 원소의 인덱싱이 선형적인 관계를 가지는 것들이라 생각하면 쉽다. 연결 구조를 나타낼 수만 있으면 그래프가 되기 때문에 배열, 행렬도 모두 그래프가 된다. 모든 지점.. 2023. 3. 15. 다음 728x90