토픽 43 / 82

헝가리안 알고리즘 (Hungarian Algorithm)

이분 그래프에서 최소 비용 최대 매칭(최적 할당)을 O(V³) 시간에 구하는 알고리즘으로, 비용 행렬을 조작하여 최적 할당을 찾는 조합 최적화 기법

목적: 최소 비용 할당, 가중 이분 매칭, 작업-자원 최적 배정

특징: 다항 시간 O(V³), 최적해 보장, 비용 행렬 기반, Kuhn-Munkres 알고리즘이라고도 함

동작 과정

시간 복잡도: O(V³), V = 정점 수 (작업자 또는 작업 수)

공간 복잡도: O(V²) - 비용 행렬

장점: 최적해 보장, 다항 시간, 실용적 성능

단점: 정방 행렬 필요(비정방은 더미 추가), 대규모 문제 시 O(V³) 부담

적용사례: 작업 배정(작업자→작업), 자원 할당, 운송 문제, 추적 시스템(객체 매칭), 스케줄링

비교: 헝가리안(최소비용/O(V³)/최적) vs 증가경로(최대매칭/O(VE)/비가중) vs 경매 알고리즘(분산/근사)

연관: 이분 매칭, 할당 문제, 비용 행렬, 조합 최적화, 네트워크 플로우