안정 매칭(게일–섀플리) 계산기
양쪽의 선호 순위를 넣으면 서로 지금 짝보다 상대를 더 좋아하는 쌍이 없도록 짝을 지어 줍니다. 어느 쪽이 청혼하느냐에 따라 답이 달라지므로 두 방향을 모두 돌려 나란히 보이고, 안정성도 모든 쌍을 훑어 직접 검산합니다.
한 줄에 「이름: 1순위 2순위 …」 하나씩. 12명까지.
상대편 전원을 빠짐없이 적어야 합니다.
4명씩 짝짓기
4명의 짝이 달라집니다
청혼하는 쪽은 안정 매칭 가운데 자기가 얻을 수 있는 최선을, 받는 쪽은 최악을 얻습니다. 절차는 대칭인데 결과는 대칭이 아닙니다.
두 방향을 나란히
| 위쪽 명단 | 위쪽이 청혼 | 아래쪽이 청혼 |
|---|---|---|
| m1 | w11순위 | w44순위 |
| m2 | w21순위 | w34순위 |
| m3 | w31순위 | w24순위 |
| m4 | w41순위 | w14순위 |
| 회차 | 청혼 | 결과 |
|---|---|---|
| 1 | m1 → w1 | 받아들임 |
| 2 | m2 → w2 | 받아들임 |
| 3 | m3 → w3 | 받아들임 |
| 4 | m4 → w4 | 받아들임 |
짝이 없는 사람이 아직 청혼해 보지 않은 상대 중 가장 좋아하는 쪽에게 청혼하고, 받는 쪽은 지금 짝과 견줘 더 좋아하는 쪽을 잡습니다. 밀려난 사람은 다시 줄에 서서 다음 순위로 내려갑니다. 4명이면 청혼은 많아야 16번이라 반드시 끝납니다.
계산 방법
- 1한쪽 명단을 「이름: 1순위 2순위 …」 형식으로 한 줄씩 적습니다.
- 2다른 쪽 명단도 같은 형식으로 적습니다. 상대편 전원을 빠짐없이 넣어야 합니다.
- 3두 방향의 결과가 몇 명이나 달라지는지 확인합니다.
- 4표에서 각자가 몇 순위 상대와 짝이 됐는지 견줍니다.
- 5청혼 과정을 보며 누가 언제 밀려났는지 따라갑니다.
자주 묻는 질문
불안정한 쌍이 하나도 없는 짝짓기입니다. 불안정한 쌍이란 서로 지금 짝보다 상대를 더 좋아하는 두 사람으로, 그런 쌍이 있으면 둘이 지금 짝을 버리고 붙어 버릴 것이므로 그 배정은 유지되지 않습니다.
짝이 없는 사람이 아직 청혼해 보지 않은 상대 중 가장 좋아하는 쪽에게 청혼하고, 받는 쪽은 지금 짝과 견줘 더 좋아하는 쪽을 잡고 나머지를 놓아 줍니다. 밀려난 사람은 다시 줄에 서서 다음 순위로 내려갑니다. 사람이 n명이면 청혼은 많아야 n²번이라 반드시 끝납니다.
달라집니다. 청혼하는 쪽은 안정 매칭 가운데 자기가 얻을 수 있는 최선을, 받는 쪽은 최악을 얻습니다. 청혼하는 쪽은 가장 좋아하는 상대부터 내려가므로 거절당하지 않는 한 아래로 갈 이유가 없고, 받는 쪽은 더 좋은 청혼이 올 때만 갈아탈 뿐 먼저 고를 수 없기 때문입니다. 절차는 대칭인데 결과는 대칭이 아닙니다.
중립적인 답이 없습니다. 「누가 지원하고 누가 뽑는가」를 정하는 일이 곧 누구에게 유리한 규칙을 고르는 일입니다. 인턴 배정이나 전공 배정처럼 실제로 쓰이는 자리에서 이 선택이 논쟁거리가 되는 이유이고, 이 도구가 두 방향을 함께 보이는 이유이기도 합니다.
양쪽 인원이 같고 각자가 상대편 전원을 순위에 넣는다면 반드시 있습니다. 게일–섀플리가 언제나 하나를 찾아 주기 때문입니다. 다만 하나뿐이라는 뜻은 아니고 여러 개일 수 있으며, 이 도구는 두 방향을 돌려 그중 양 극단을 보여 줍니다.
게일과 섀플리가 1962년에 낸 이 알고리즘이 2012년 노벨경제학상(섀플리·로스)의 근거가 되었습니다. 로스가 이 이론을 미국 전공의 배정과 신장 교환 프로그램에 실제로 적용한 것이 함께 평가받았습니다.
이 도구는 알고리즘을 믿지 않고 모든 쌍을 훑어 불안정한 쌍을 직접 세어 봅니다. 알고리즘과 원리가 겹치지 않는 검사라 둘이 어긋나면 어딘가 틀린 것이고, 화면에 그 결과를 함께 표시합니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 정답지는 전수 탐색입니다. 사람이 n명이면 짝짓는 방법이 n!가지뿐이므로 작은 판에서는 전부 만들어 볼 수 있고, 그중 불안정한 쌍이 없는 것들이 안정 매칭입니다. 게일–섀플리가 낸 답이 그 목록 안에 있는지 확인합니다.
- 「청혼하는 쪽이 최선을, 받는 쪽이 최악을 얻는다」도 전수 탐색으로 확인했습니다. 안정 매칭 전체에서 청혼하는 쪽의 순위 합이 가장 작고 받는 쪽의 순위 합이 가장 큰 것이 게일–섀플리의 결과와 일치합니다. 알고리즘은 이 성질을 전혀 쓰지 않고 돌기 때문에 서로를 검산해 줍니다.
- 무작위 선호 순위 200판(3~5명)에서 위 세 가지를 모두 확인했습니다. 안정할 것, 전수 탐색 목록에 있을 것, 양 극단일 것입니다.
- 청혼 횟수가 인원의 제곱을 넘지 않는 것, 밀려난 사람이 반드시 다시 청혼하는 것도 테스트로 고정했습니다.
- 불안정한 쌍을 찾는 검사기는 알고리즘을 전혀 쓰지 않고 모든 쌍을 훑습니다. 일부러 엇갈리게 붙인 배정에서 불안정한 쌍을 제대로 잡아내는지도 확인했습니다.
- 양쪽 인원이 같고 각자가 상대편 전원을 순위에 넣어야 합니다. 어긋나면 무엇이 빠졌는지 짚어 답합니다. 인원은 12명까지 다룹니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.