알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17481 17481번: 최애 정하기 1번 친구가 SOOJIN, 2번 친구가 SOYEON, 3번 친구가 YUQI, 4번 친구가 SHUHUA, 5번 친구가 MIYEON을 최애 멤버로 정하면 친구들이 최대로 좋아할 수 있는 멤버 수는 5명이 된다. www.acmicpc.net 이분 매칭으로 쉽게 풀 수 있는 문제입니다. 이분 그래프에서 두 그룹을 X, Y그룹이라고 할 때, 모든 경로의 방향이 X -> Y인 그래프의 최대 유량을 구하는 것이 이분 매칭입니다. 문제에서 볼 수 있듯이, 이분 매칭을 통해 구하고자 하는 것은 최대 매칭 수입니다. 이때 매칭한다는 것은 1대 1함수와 같이 하나의 정점이 다른 그룹의 하나의 정점만을 점유하고 있..

문제 링크입니다. https://www.acmicpc.net/problem/11377 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net 이분 매칭을 이용한 문제입니다. 해당 문제에서 응용된 문제입니다. https://junseok.tistory.com/339 백준 11375 - 열혈강호(C++) 문제 링크입니다. https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원..

문제 링크입니다. https://www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net 이분 매칭을 이용하는 문제입니다. 해당 문제에서 응용된 문제입니다. https://junseok.tistory.com/339 백준 11375 - 열혈강호(C++) 문제 링크입니다. https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매..

문제 링크입니다. https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 이분 매칭을 이용하는 문제입니다. 이분 매칭이라는 알고리즘 설명이 잘나와있는 블로그입니다. 참고해주세요. https://yjg-lab.tistory.com/209 [알고리즘] 이분 매칭 알고리즘 (Bipartite Matching) 이분 매칭 알고리즘 (Bipartite Matching) 두 개의 정점 그룹이 존재할 때 모든 간선(경로)의 용량이 1이면서 양쪽 정점이 서로 다른 그룹..

문제 링크입니다. https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 이분 매칭을 사용하는 문제입니다. 이분 그래프에서 두 그룹을 X, Y그룹이라고 할 때, 모든 경로의 방향이 X -> Y인 그래프의 최대 유량을 구하는 것이 이분 매칭입니다. 문제에서 볼 수 있듯이, 이분 매칭을 통해 구하고자 하는 것은 최대 매칭 수입니다. 이때 매칭한다는 것은 1대 1함수와 같이 하나의 정점이 다른 그룹의 하나의 정점만을 점유하고 있는 상태를 말합니다. ..