공부공간

www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각�� www.acmicpc.net 직원그룹과 해야할일그룹 두 그룹간에 매칭을 시켜주는 전형적인 이분매칭 문제이다. 1 ) 현재를 이을것인지? 2 ) 이어진 현재를 바꿔서 나를 이을것인지? 의 두가지를 구현하면되는데, 재귀함수로 구현할 수 있다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.ut..

https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해� www.acmicpc.net 각 소가 원하는 축사가 존재한다 ( 존재하지 않을수도 있음 ) 일단은 배정후 변경하는 이분매칭알고리즘을 사용하자. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; class Main { public static int m,..

https://www.acmicpc.net/problem/1298 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net 이분 매칭의경우 네트워크플로우에서 최대유량이 1인간선으로 이루어진 네트워크중 A/B집합 두개로 나뉘어서 최대유량을 구하는 문제이다. 하지만 에드몬드카프로 구현하기보다는 DFS를 활용하여, 앞선 매칭을 바꿀수있는지? 에대한 재귀함수를 정의한다. 이해가 안되면 아래 강의를 추천한다. 뭔가 이분매칭의경우, "두 집합간 최대한 매칭을 시킨다" 라는 느낌이 온다. https://blog.naver.co..