01 · Intro
"짝을 맺는다"는 문제, 생각보다 깊습니다.
Tinder의 스와이프, 의대생 레지던트 배정, 배달앱 라이더 배차, Uber Pool. 이 모두가 사실 같은 질문을 풉니다 — 누구와 누구를 짝지을까?
💜
Tinder / Bumble
양쪽이 Like할 때만 매칭 — 상호 합의
🎓
의대 레지던트
Gale-Shapley로 안정 매칭 (1962~)
🛵
배달의민족 / 쿠팡이츠
주문 ↔ 라이더 이분 매칭
🚕
Uber / 카카오T
총비용 최소 할당 — Hungarian
02 · 스와이프 매칭 — Tinder처럼
가장 단순한 매칭 규칙은 상호 합의입니다. 양쪽이 모두 Like를 눌렀을 때만 매칭이 성립합니다.
03 · 안정 매칭 — Gale-Shapley
여러 제안자와 여러 수신자, 각자 선호 순서가 있을 때 차단 쌍이 없는 안정 매칭을 만드는 1962년 알고리즘입니다. 2012년 노벨 경제학상을 받은 이 아이디어가 미국 의대 레지던트 배정의 기반이 됩니다.
04 · 이분 매칭 — 증강 경로
선호도는 없지만 "이 사람은 저 일만 할 수 있다" 같은 가능성 제약이 있을 때. 배달앱 라이더↔주문, 면접관↔지원자 배정처럼요. 핵심 도구는 증강 경로(augmenting path)입니다.
05 · 할당 — Hungarian
각 일마다 비용이 다를 때, 전체 비용의 합이 최소가 되도록 일을 사람에게 배정합니다. 배달앱이 "어느 라이더를 어느 주문에?"를 결정할 때 쓰는 원리의 고전 버전입니다.