안정 결혼 문제 (Stable Marriage Problem) 는 N 명의 남성과 N 명의 여성이 각자 선호도 목록을 가지고 있을 때, 모든 쌍이 안정적 (stable) 인 매칭을 찾는 문제. Gale-Shapley 알고리즘 (1962, Nobel 2012) 은 O(N^2) 에 항상 안정 매칭을 찾는다. 안정적 = 어떤 (m, w) 도 현재 자신의 짝보다 상대를 더 선호하지 않는 상태.
문제 상황과 동기
naive: 모든 매칭 N! 가지를 검사 -> O(N!), N=10 에도 불가능.
핵심 통찰: 제안 (proposal) 과정을 통해 불안정 쌍을 반복 제거. proposer 쪽이 최적의 결과를 얻는다.
Gale-Shapley: 매 라운드 미매칭 proposer 가 가장 선호하는 상대에게 제안. reject 되면 다음 선호로. 최대 N^2 라운드 이내 종료.
실제 활용: 전국 레지던트 매칭 (NRMP), 학교 배정, 장기 매칭.
시각화
핵심 아이디어
invariant: proposer 의 매칭은 단조 하락 (점점 덜 선호하는 쪽으로). receiver 의 매칭은 단조 상승 (점점 더 선호하는 쪽으로).
프로세스:
모든 남성이 첫 번째 선호 여성에게 제안
여성은 가장 선호하는 제안자와 약혼 (나머지 reject)
reject 된 남성은 다음 선호 여성에게 제안
여성은 현재 약혼자와 새 제안자 중 더 선호하는 쪽 선택
모두 매칭될 때까지 반복 -> 최대 O(N^2) 라운드
알고리즘
Gale-Shapley(M, W, menPref, womenPref): womanMatch[1..N] = -1 manNext[1..N] = 1 freeMen = queue of all men while freeMen not empty: m = freeMen.pop() w = menPref[m][manNext[m]++] if womanMatch[w] == -1: womanMatch[w] = m else: m2 = womanMatch[w] if womenPref[w][m] < womenPref[w][m2]: womanMatch[w] = m freeMen.push(m2) else: freeMen.push(m) return womanMatch (or manMatch from it)
구현
// Gale-Shapley O(N^2) stable matching#include <bits/stdc++.h>using namespace std;int main() { int N; cin >> N; vector<vector<int>> menPref(N, vector<int>(N)); vector<vector<int>> womenPref(N, vector<int>(N)); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> menPref[i][j]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> womenPref[i][j]; // 여성의 선호도 순위 lookup table vector<vector<int>> rank(N, vector<int>(N)); for (int w = 0; w < N; w++) for (int r = 0; r < N; r++) rank[w][womenPref[w][r]] = r; vector<int> matchW(N, -1), nxt(N, 0); queue<int> q; for (int m = 0; m < N; m++) q.push(m); while (!q.empty()) { int m = q.front(); q.pop(); int w = menPref[m][nxt[m]++]; if (matchW[w] == -1) { matchW[w] = m; } else { int m2 = matchW[w]; if (rank[w][m] < rank[w][m2]) { matchW[w] = m; q.push(m2); } else { q.push(m); } } } vector<int> matchM(N); for (int w = 0; w < N; w++) matchM[matchW[w]] = w; for (int m = 0; m < N; m++) cout << m << " " << matchM[m] << "\n"; return 0;}
def gale_shapley(men_pref, women_pref): N = len(men_pref) rank = [[0] * N for _ in range(N)] for w in range(N): for r, m in enumerate(women_pref[w]): rank[w][m] = r match_w = [-1] * N nxt = [0] * N free_men = list(range(N)) while free_men: m = free_men.pop(0) w = men_pref[m][nxt[m]] nxt[m] += 1 if match_w[w] == -1: match_w[w] = m else: m2 = match_w[w] if rank[w][m] < rank[w][m2]: match_w[w] = m free_men.append(m2) else: free_men.append(m) match_m = [0] * N for w, m in enumerate(match_w): match_m[m] = w return match_mN = int(input())men_pref = [list(map(int, input().split())) for _ in range(N)]women_pref = [list(map(int, input().split())) for _ in range(N)]match = gale_shapley(men_pref, women_pref)for m, w in enumerate(match): print(m, w)
import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[][] menPref = new int[N][N]; int[][] womenPref = new int[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) menPref[i][j] = sc.nextInt(); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) womenPref[i][j] = sc.nextInt(); int[][] rank = new int[N][N]; for (int w = 0; w < N; w++) for (int r = 0; r < N; r++) rank[w][womenPref[w][r]] = r; int[] matchW = new int[N]; Arrays.fill(matchW, -1); int[] nxt = new int[N]; Queue<Integer> q = new LinkedList<>(); for (int m = 0; m < N; m++) q.add(m); while (!q.isEmpty()) { int m = q.poll(); int w = menPref[m][nxt[m]++]; if (matchW[w] == -1) { matchW[w] = m; } else { int m2 = matchW[w]; if (rank[w][m] < rank[w][m2]) { matchW[w] = m; q.add(m2); } else { q.add(m); } } } int[] matchM = new int[N]; for (int w = 0; w < N; w++) matchM[matchW[w]] = w; for (int m = 0; m < N; m++) System.out.println(m + " " + matchM[m]); }}
💬 댓글