푸으름

✏️문제 링크 https://www.acmicpc.net/problem/14433 14433번: 한조 대기 중 첫째 줄에 한 팀에 속한 플레이어의 수 N(1 ≤ N ≤ 300)과 트롤픽의 수 M(1 ≤ M ≤ 300), 각 팀의 팀원들이 원하는 트롤픽의 수 K1, K2(1 ≤ K1, K2 ≤ 500)가 주어진다. 다음 K1개의 줄에 걸쳐 두 수 i, j(1 ≤ www.acmicpc.net ✏️문제 설명 ✏️문제 풀이 두 팀이므로 각 팀마다 이분 매칭을 구현해주면 됩니다. https://pooreumjung.tistory.com/338 Algorithm 공부 #26 - 이분 매칭(Binary Matching) Algorithm 공부 #26 - 이분 매칭 ✏️이분 매칭이란? 이분 그래프에서 주로 사용하는 알..

✏️문제 링크 https://www.acmicpc.net/problem/1671 1671번: 상어의 저녁식사 어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크 www.acmicpc.net ✏️문제 설명 ✏️문제 풀이 이분매칭으로 구현하는 문제이고 다만 조금은 생각을 해봐야하는 부분들이 있습니다. 일반적인 이분매칭은 그냥 입력받는 간선 정보를 그대로 이분 그래프로 구현하면 되는 반면, 이 문제는 상어들이 잡아먹을 수 있는 조건들이 있기 때문에 그 점들을 고려해야 합니다. 그래서 저는 아래와 같이 조건을 구성했습니다. 각 상어들을 A와 B라고 할 때 1. A..

✏️문제 링크 https://www.acmicpc.net/problem/1298 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 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과 연결(총..