[462] 이분 매칭 알고리즘(파이썬 코드)
위와 같은 이분 그래프가 있을 때 이분 매칭을 구해봅시다. 1. 종만북 참고 소스코드종만북 코드는 C언어이므로 파이썬 코드로 옮기면 다음과 같습니다.n, m = 5, 5adj = [ [1, 1, 1, 1, 1], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 1], ]a_match, b_match = [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1]def dfs(a): if visited[a]: return False visited[a] = True for b in range(m): if adj[a][b]: if b_match[b]..
[461] 여러 수열에서 수 하나씩 골라 최소 범위 만들기
1. 문제수열이 여러 개(N개) 있을 때, 각 수열에서 수를 하나씩만 고릅니다.그렇게 고른 수 중 최대값과 최소값의 차이가 가장 작게 골라봅시다.예를 들어, {49, 97, 1, 64, 25}, {93, 33, 54, 78, 12}, {71, 6, 80, 20, 44}가 있을 때, 각 수열에서 수 하나씩 고릅니다.이 때 만약 첫 번째 수열에서 49, 두 번째 수열에서 54, 세 번째 수열에서 44를 고른다면, 이 중 최대값인 54와 최소값인 44의 차이는 10입니다.이렇게 선택한 수 중 최대값과 최소값의 차이가 가장 작게 고르는 방법을 알아봅시다.2. 해결 방법가. Brute-force모든 경우의 수를 일일이 살펴보고, 정답을 찾는 방법입니다.구현하기 가장 쉽지만, 비효율적입니다.시간복잡도를 계산해보면 ..
