게일 섀플리 알고리즘(Gale–Shapley algorithm)

수학이 필요한 순간

 

김민형 작가가 쓴 수학이 필요한 순간을 읽고 있다. 본문 5장에 소개되는 알고리즘으로, 게일 섀플리 알고리즘이라는 것이 있다. 남자 n명과 여자 n명이 소개팅을 할 때, 짝을 지어주는 최적의 방법을 찾아주는 알고리즘이다. 그러기 위해서는 각 남자가 어떤 여자를 좋아하는 지 순위를 매긴 정보가 필요하다. 이를 테면 n이 4일 때 1번 남자는 1번 여자-4번 여자-3번여자-2번여자 순서대로 좋다는 정보를 말한다. 그리고 반대로 각 여자가 남자들의 순위를 매긴 정보도 필요하다.

 

문제는 이 때 어떻게 짝을 맺어주어야 안정적인 커플 네 쌍이 생기냐는 것이다.

 

1번 여자와 3번 남자가 이어졌고, 2번 여자와 4번 남자가 이어졌다고 가정했을 때, 1번 여자는 3번 남자보다 4번 남자가 좋고 4번 남자는 2번 여자보다 1번 여자가 좋으면 1번 여자는 3번 남자를 버리고 4번 남자에게 갈 것이다. 4번 남자 역시 2번 여자를 버리고 1번 여자에게 갈 것이다. 안정적이지 못하다. 따라서 위 방법은 문제의 해가 아니다.

 

게일 섀플리 알고리즘은 문제의 해 중 1개를 찾아주는 알고리즘이다. (모두 찾는 게 아니다. 수많은 가능한 해들 중 1개만 찾는다.)

 

일단, 남자들은 모두 자신의 1순위 여자에게 청혼을 한다. 여자들은 받은 청혼 중 가장 마음에 드는 (가장 순위 높은) 남자와 약혼한다.

 

짝을 찾지 못한 남자들은 이제 자신의 2순위 여자에게 청혼을 한다. 여자들은 본인에게 청혼한 남자가 현재의 짝보다 마음에 들면 약혼을 깨고 그 청혼을 받을 수 있다.

 

짝을 찾지 못한(또는 약혼이 깨어져 짝이 없어진) 남자는 다음 순위 여자에게 청혼을 하고, 여자는 마음에 드는 남자의 청혼을 받는다.

 

이것을 반복하면 안정된 짝 n쌍이 생긴다.

 

 

 

 

Q. 모두가 짝을 찾을 수 있다는 것이 보장되는지?

 

귀류법을 이용해 증명할 수 있다.

 

짝을 못 찾은 남자가 최소 1명 있다고 가정하자(남자 X). 그럼 짝을 못 찾은 여자 Y도 1명 존재한다. 남자 X는 짝을 찾을 때까지 청혼을 하기 때문에 짝을 못 찾았다면 더 이상 청혼할 사람이 없는 상태이다. 여자 Y는 청혼을 한 번도 받지 못했어야 한다. 청혼을 한 번이라도 받았다면 짝이 있었을 것이기 때문이다. 그런데 남자 X는 여자 Y에게 청혼을 하지 않았다면 청혼할 사람이 더 이상 없다는 것에 모순이다. 따라서 짝을 못 찾은 남자 X는 존재하지 않는다.

 

Q. 모든 짝이 안정적인가?

책 참고.

 

이 알고리즘을 이용해 푸는 코딩 PS 문제가 백준에 존재한다. 바로 12022번 짝 문제다.

https://www.acmicpc.net/problem/12022

 

해법은 나중에 첨부하겠다.