푸으름

✏️문제 링크 https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net ✏️문제 설명 ✏️문제 풀이 기본적인 이분 매칭 구현 문제입니다. 이분 매칭 알아보기 https://pooreumjung.tistory.com/338 Algorithm 공부 #26 - 이분 매칭(Binary Matching) Algorithm 공부 #26 - 이분 매칭 ✏️이분 매칭이란? 이분 그래프에서 주로 사용하는 알고리즘 이분 그래프는 두 개의 정점 그룹이 존재할 때 모든 간선의 ..

✏️ 문제 링크 https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 기본적인 이분 매칭 구현 문제입니다. 이분 매칭이 먼지 잘 모르시겠다면? https://pooreumjung.tistory.com/338 Algorithm 공부 #26 - 이분 매칭(Binary Matching) Algorithm 공부 #26 - 이분 매칭 ✏️이분 매칭이란? 이분 그래프에서 주로 사용하는 알고리즘 이분 그래프는 두 개의 정점..

Algorithm 공부 #26 - 이분 매칭 ✏️이분 매칭이란? 이분 그래프에서 주로 사용하는 알고리즘 이분 그래프는 두 개의 정점 그룹이 존재할 때 모든 간선의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프 이러한 이분 그래프에서 예를 들어, 한 그룹은 X그룹, 다른 한 그룹은 Y그룹이고 간선의 방향은 X->Y라고 할 때 모든 경로의 방향은 X->Y인 그래프의 최대 유량을 구하는 것 ✏️예시 먼저 알파벳 그룹과 숫자 그룹이 있다고 가정을 하면 A에서 갈 수 있는 숫자는 1과 3 B에서 갈 수 있는 숫자는 1과 2 C에서 갈 수 있는 숫자는 5 D에서 갈 수 잇는 숫자는 3 E에서 갈 수 있는 숫자는 2 A부터 매칭을 시작하면 각 점에서는 한 개의 숫자만 갈 수 있으므로 A는 1과 연결(총..