반응형 이분매칭3 백준 11376번 열혈강호 2 - C++(cpp) 풀이 1. 할 수 있는 일의 최대 개수는, 최대 매칭의 수와 같다. 2. 각 직원당 최대 2개의 일을 할 수 있으므로, 이분 매칭을 2번 진행한다. 1. 할 수 있는 일의 최대 개수는, 최대 매칭의 수와 같다. 직원 그룹과 일 그룹 사이의 최대 매칭의 수를 구하는 문제이다. 2. 각 직원당 최대 2개의 일을 할 수 있으므로, 이분 매칭을 2번 진행한다. 각 직원당 최대 2개의 일을 할 수 있으므로, 직원을 기준으로 하는 이분 매칭을 2번 진행하여 이루어진 총 매칭의 수를 구해주면 된다. #include #include #include using namespace std; const int MAX = 1001; int N, M; vector works[MAX]; int owner[MAX]; bool visit[.. 2022. 5. 27. 백준 11375번 열혈강호 - C++(cpp) 풀이 1. 직원과 일 사이의 관계를 이분 그래프로 만든다. 2. 이분 매칭 알고리즘을 사용하여 직원 정점 그룹과 일 정점 그룹 사이의 최대 매칭수를 찾는다. 1. 직원과 일 사이의 관계를 이분 그래프로 만든다. 각 직원과 일을 정점으로 생각하고, 각 직원과 그 직원이 할 수 있는 일들을 간선으로 이어 이분 그래프를 만든다. 2. 이분 매칭 알고리즘을 사용하여 직원 정점 그룹과 일 정점 그룹 사이의 최대 매칭수를 찾는다. 최대로 할 수 있는 일의 개수는, 완성된 이분 그래프에서 직원 그룹과 일 그룹 사이의 최대 매칭의 수와 같다. 따라서 이분 매칭 알고리즘을 사용해 최대 매칭 수를 구해주면 된다. #include #include #include using namespace std; const int MAX = .. 2022. 5. 23. 백준 18138번 리유나는 세일러복을 좋아해 - 스위프트(Swift) 풀이 1. 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍에 대해 간선으로 연결한다. 2. 티셔츠와 카라를 이분 매칭 한다. 1. 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍에 대해 간선으로 연결한다. 티셔츠 집단과 카라 집단을 최대로 매칭 시켜야 하는 이분 매칭 문제이다. 먼저 각 티셔츠와 카라들을 그래프의 정점이라고 생각한 뒤, 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍을 간선으로 연결해 그래프를 만들어준다. 2. 티셔츠와 카라를 이분 매칭 한다. 이제 완성된 그래프에 대해 이분 매칭을 진행하면 된다. DFS를 사용하여 구현하였다. import Foundation var N = 0, M = 0 var Tshirts = Array(repeating: 0, count: 201) var co.. 2022. 3. 8. 이전 1 다음 반응형
