매칭 알고리즘: 이분 매칭·Hungarian·안정 매칭의 선택 기준
이분 매칭, Hungarian 알고리즘, Gale–Shapley 안정 매칭의 모델링 방식과 복잡도, 인력 배정·배송·레지던트 배치 적용 기준을 정리합니다.
2026-08-14 · 최초 발행 2024-04-29
매칭의 목적은 모두 같지 않다
매칭은 두 집합의 요소, 또는 하나의 집합 안의 요소를 규칙에 따라 짝지어 전체 효용을 높이거나 제약을 만족시키는 문제다. 인력과 작업, 드라이버와 요청, 병원과 지원자처럼 연결 후보가 여럿일 때 어떤 기준을 우선하느냐에 따라 문제의 형태가 달라진다.
이분 매칭은 이분 그래프에서 노드를 공유하지 않는 엣지 집합을 찾는다. 최대 매칭이나 완전 매칭이 대표적인 변형이다. 반면 할당 문제는 비용 또는 보상 행렬을 이용한 1:1 매칭에서 총비용 최소화나 이익 최대화를 구하며, Hungarian 알고리즘이 대표 해법이다. 안정 결혼 문제는 양측 선호가 주어졌을 때 불안정 쌍이 생기지 않도록 매칭을 구성하고, Gale–Shapley 알고리즘으로 풀 수 있다.
모델링 단계에서는 먼저 최대 카디널리티, 비용 최소화, 안정성 가운데 무엇이 본체인지 정한다. 이어 그래프·행렬·선호 목록으로 입력을 구조화하고, 제약·가중치·정책을 반영하는 절차를 잡는다.
입력 구조와 목적 함수가 알고리즘을 가른다
이분 그래프의 노드와 엣지, 비용 행렬, 선호 목록은 서로 다른 문제 표현이다. 입력을 해당 구조로 정규화한 뒤 목적 함수를 정한다. 최대 카디널리티, 최소 비용, 안정성 보장 중 하나를 선택할 수도 있고 다목적 최적화로 구성할 수도 있다.
용량, 지역 또는 시간 윈도, 공정성 정책, 자격 요건은 하드 제약과 소프트 제약으로 나눠 반영한다. 매칭 수가 최우선이고 비용이나 선호가 부차적이면 Bipartite Matching이 맞다. 비용 최소화나 이익 최대화가 우선인 할당 문제에는 Hungarian Algorithm이 적합하다. 상호 안정성, 포용성, 공정성이 핵심인 시장이나 인사 배치에서는 Stable Marriage를 선택한다.
Hopcroft–Karp의 복잡도는 O(E·√V)이며 대규모 희소 그래프에 유리하다. Hungarian 알고리즘은 n×n 비용 행렬에서 O(n^3)이고, 비용 품질을 보장하는 안정적인 방식이다. Gale–Shapley는 O(n^2)이며 선호 목록 길이에 선형으로 동작하고 정책 변형이 쉽다.
비용과 카디널리티를 함께 다뤄야 하면 Hungarian 또는 최소비용 유량(MCMF)으로 확장할 수 있다. 선호와 안정성을 결합할 때는 Gale–Shapley를 기본으로 두고 타이, 불완전 목록, 쿼터에 맞는 변형 알고리즘을 적용한다. 여러 목적이 있으면 가중 합 목적함수, 사전식 최적화, 제약 충족 후 보조 최적화를 사용할 수 있다.
| 알고리즘 | 성능 | 확장성 | 일관성 | 안정성 | 운영 편의 |
|---|---|---|---|---|---|
| Bipartite Matching (Hopcroft–Karp) | O(E·√V), 카디널리티 최적 | 희소 그래프에 강함, 분산화 용이 | 결정적 결과, 재현성 높음 | 안정성 미보장, 비용 무시 시 적합 | 구현 간단, NetworkX 등 풍부 |
| Hungarian Algorithm | O(n^3), 비용 최적 | n 대 n 스케일에서 안정적 | 결정적, 전역 최적 보장 | 안정성 미보장(선호 충돌 가능) | SciPy 등 표준 라이브러리 제공 |
| Stable Marriage (Gale–Shapley) | O(n^2), 선호 기반 | 선호 목록 길이에 선형 | 결정적(제안측 유리성), 재현 가능 | 안정성 보장, 비용 최적 아님 | 구현 용이, 정책 변형 쉬움 |
입력 검증부터 결과 산출까지
배정 업무에서 달라지는 모델
인력-작업 할당에서는 작업×인력 비용 행렬과 가용 시간, 자격 제약을 입력으로 둔다. Hungarian 알고리즘으로 최소 비용의 완전 또는 부분 할당을 구하고, 균형이 맞지 않으면 더미를 추가한다. 결과는 총비용이 최소인 배정표와 미배정 작업·인력 목록으로 정리된다.
라이드헤일링이나 배송에서는 드라이버와 요청 사이의 거리·ETA를 가중 엣지로 만들고 시간 윈도 제약을 적용한다. 짧은 배치 윈도에서는 Hungarian 또는 최소비용 유량을 사용할 수 있으며, 대규모 실시간 스트림에는 Hopcroft–Karp 변형을 적용한다. 한 배치 라운드의 최적 매칭과 SLA 위반 후보 경보가 결과가 된다.
의료 레지던트 배치는 병원과 지원자의 선호 목록, 병원별 쿼터를 기반으로 한다. 병원 쿼터 확장을 적용한 Gale–Shapley로 안정 매칭을 구하고, 동점과 우선순위 규칙을 반영한다. 안정 배치 결과와 탈락자·대기자 목록을 함께 산출한다.
최대 매칭을 구하는 Hopcroft–Karp
# Python 3.10+, pip install networkx
import networkx as nx
# 좌우 파티션
left = {"A", "B", "C"}
right = {"1", "2"}
G = nx.Graph()
G.add_nodes_from(left, bipartite=0)
G.add_nodes_from(right, bipartite=1)
G.add_edges_from([("A","1"), ("A","2"), ("B","2"), ("C","1")])
# 유효성 검사: 이분성 보장
if not nx.is_bipartite(G):
raise ValueError("이분 그래프가 아님")
matching = nx.algorithms.bipartite.matching.hopcroft_karp_matching(G, top_nodes=left)
# matching은 양방향 매핑 포함 → 좌측 기준 정리
result = {u: v for u, v in matching.items() if u in left}
print(result) # 예: {'A': '2', 'C': '1'}가중치 기반 최적화가 필요하면 minimum_cost_flow 또는 Hungarian을 적용한다. 파티션 크기가 불균형해도 최대 매칭 수는 |right|를 초과하지 않는다.
비용 행렬을 다루는 Hungarian 알고리즘
# Python 3.10+, pip install numpy scipy
import numpy as np
from scipy.optimize import linear_sum_assignment
# 비용 행렬 (작업 x 인력). 불균형 시 더미 열/행과 큰 비용(예: 1e6)으로 패딩
cost = np.array([[9, 2, 7],
[6, 4, 3],
[5, 8, 1]])
row_ind, col_ind = linear_sum_assignment(cost)
total = cost[row_ind, col_ind].sum()
assignment = list(zip(row_ind, col_ind))
print("assignment:", assignment) # (작업 i, 인력 j)
print("total_cost:", total)최대 이익 문제는 비용 = -이익 변환 또는 max→min 변환으로 바꿔 처리한다. 부분 할당을 허용한다면 더미 노드로 패딩한 뒤 더미 배정을 미배정으로 해석한다.
선호 충돌을 줄이는 Gale–Shapley
# Python 3.10+
from collections import deque
def gale_shapley(men_prefs: dict[str, list[str]], women_prefs: dict[str, list[str]]):
# 여성 선호 순위 매핑
rank = {w: {m: i for i, m in enumerate(prefs)} for w, prefs in women_prefs.items()}
free = deque(men_prefs.keys())
next_proposal = {m: 0 for m in men_prefs}
engaged = {} # woman -> man
while free:
m = free.popleft()
prefs = men_prefs[m]
if next_proposal[m] >= len(prefs):
continue # 제안할 대상 없음 → 미배정
w = prefs[next_proposal[m]]
next_proposal[m] += 1
if w not in engaged:
engaged[w] = m
else:
current = engaged[w]
if rank[w].get(m, float('inf')) < rank[w].get(current, float('inf')):
engaged[w] = m
free.append(current)
else:
free.append(m)
# 결과 매핑: man->woman
return {man: woman for woman, man in engaged.items()}
men = {"A": ["x", "y", "z"], "B": ["y", "x", "z"], "C": ["y", "z", "x"]}
women = {"x": ["B", "A", "C"], "y": ["A", "C", "B"], "z": ["A", "B", "C"]}
print(gale_shapley(men, women))선호 목록에 타이 또는 누락이 있다면 무작위나 우선순위 같은 타이브레이크 규칙을 사전에 합의해야 한다. 쿼터가 있으면 여성 노드를 좌석 수만큼 복제하거나 병원-레지던트 변형 알고리즘을 사용한다.
운영에서 확인할 효과와 한계
Hungarian 기반 할당은 총비용을 515% 절감하고 처리 지연을 2040% 줄일 수 있다. Gale–Shapley는 차선호 역전을 방지하고 불안정 쌍 0을 보장한다. Hopcroft–Karp는 대규모 실시간 스트림 매칭을 처리할 수 있으며, 배치 윈도를 슬라이딩해 탄력적으로 운영할 수 있다.
문제 유형을 카디널리티·비용·안정성으로 명확히 구분한 뒤 해당 목적에 맞는 알고리즘을 선택해야 한다. 그래프 이분성, 행렬 패딩, 선호 목록 정합성과 같은 전처리 및 에러 핸들링을 표준화하면 운영 리스크를 줄일 수 있다. 단일 알고리즘의 한계가 드러나는 경우에는 최소비용 유량, 멀티오브젝티브 최적화, 정책 규칙을 결합한 구성을 검토한다.