안정 결혼 문제(stable matching, stable marriage, gale shapley algorithm)

1. 어떻게 남녀를 맺어줘야 행복하게 살수 있을까? 결혼중매업자인 대혁에게는 200명의 고객이 있다. 100명은 남자, 100명은 여자이다. 여자 고객은 각자 남자 고객 100명을 대상으로 선호도에 따라 순위를 매겨 대혁에게 제출한다. 각자 명단의 맨 위에는 완벽한 이상형이 있고, 아래로 갈수록 호감도가 떨어져 맨 아래에는 최악의 기피남이 있다. 남자 고객 100명도 마찬가지로 여자 고객 100명을 대상으로 순위를 매겨 제출한다 대혁은 이 선호도 조사 결과를 바탕으로 남녀 고객을 맺어줘야한다. 어떻게 맺어줘야 이들이 결혼에 골인하고 가정을 이루고 오래오래 행복하게 살 수 있을까? 당연한 말이지만, 일부는 자신의 제1지망과 맺어지지 못한다.  같은 남자를 여러 여자가 제1지망으로 찍었다면 누군가는 고배를 ..