안정적인 결혼 문제 (SMP, Stable Marriage Problem)

사회 구성원 모두의 안정적인 결혼 생활을 위해(?) 고안된 알고리즘을 하나 소개하려고 한다. Stable Marriage Problem (SMP: Link) 로 불리우는 문제로 1962년에 Gale-Shapley 알고리즘에 의해 이미 풀린 문제이다. 이 링크 (Link)를 따라가서 한글 자료를 확인하고 와도 좋다. 꽤 잘 정리돼 있더라. TMA라고 소개되는 알고리즘과 동일한 알고리즘으로 문제를 해결할 것이다.

카이스트 전산학부는 석사 과정 신입생의 지도 교수 배정 과정에 이 알고리즘을 도입해서 사용하고 있다. 나도 얼마 전에 지도 교수님을 배정받으면서 선호도 리스트를 제출했었다. 근데 알고리즘을 실제로 구현하면서 시스템 상의 엄청난 문제점을 발견하기도 했고, 실로 귀찮은 디버깅이 많다는 것도 깨닫게 됐다.

---

0. 문제 정의

n명의 남자와 n명의 여자는 각자 이성들의 선호도를 나타낸 리스트를 들고 있다. 이 리스트를 통해 서로 stable한 결혼을 해야한다. 이러한 안정적인 결혼은 실제 예시를 들어 이해하면 쉽게 와닿는다. 불안정한 커플의 조건은 다음과 같다.

 - 남자 m은 자신의 현재 아내보다 다른 여자 w를 더 좋아한다. (선호도 상에서 w가 우위에 있다.)

 - 여자 w도 자신의 현재 남편보다 m을 더 좋아한다.

위 같은 상황이 벌어지면 m과 w는 각자의 배우자와 이혼한 뒤, 재혼할 것이다. 현실 세계에서 벌어지면 막장 드라마가 되기 딱 좋은 스토리가...(근데 진짜로도 꽤 많나? @_@;;;)

무튼 n명씩의 남녀가 제출한 선호도 리스트를 가지고, 서로를 결혼시켜주는 알고리즘을 고안할 것이다. 이 문제는 O( n^2 ) 에 해결할 수 있다.

하나 더 미리 언급하자면, 결혼 결과는 유일하지 않다. 그래서 유효한지 아닌지 검증하는 알고리즘도 고안할 것이다. 마찬가지로 O( n^2 )에 해결할 수 있다.

1. 안정적인 결혼 시행 알고리즘

1962년에 Gale-Shapley는 다음과 같은 과정으로 알고리즘을 고안했다.

 - 임의의 미혼 남성을 한 명 뽑는다.

 - 뽑은 남성은 자신의 선호도 리스트에서 여태 프로포즈해보지 못한 여성중 가장 선호도가 높은 여성에게 프로포즈한다.

 - 프로포즈를 받은 여성은 그 순간 약혼자가 없다면 프로포즈를 받아들여서 약혼한다. ( 아름다운 세상! )

 - 여성의 약혼자가 있다면 여성은 두 남성(이미 있던 약혼자와 프로포즈한 남성) 중 더 선호하는 남성을 골라서 약혼자를 갈아치운다. ( 약혼은 깨라고 있는거야 )

 - 이때 발생한 비운의 남성은 다시 미혼 남성으로 되돌아간다.

 - 미혼 남성이 모두 약혼했다면 그들 모두 동시에 결혼시키고 알고리즘을 종료한다.

실제 시간 순서대로 알고리즘을 시행시키다보면 별 생각이 다 든다. 세상은 저렇게 난잡하진 않겠지만 그래도...ㅜㅜ

Ref) https://goo.gl/PNKxDQ

일단 미혼 남성 모두 한 번씩 알고리즘에 참여하므로 O(n)만큼의 시간은 무조건 사용해야한다. 각각의 미혼 남성마다 자신의 선호도 리스트를 뒤적거리는 시간 O(n), 프로포즈한 여성이 그녀의 선호도 리스트를 확인해서 남성을 선택하는 데 걸리는 시간 O(1)을 소모하여 알고리즘이 종료된다.

구현 상에서 중요한 것은 O(1) 시간 안에 여성의 선호도 리스트에서 남성 둘을 비교하는 것이다. 실제로 주어진 선호도 리스트는 1위부터 n위까지의 남성이 순서대로 나열되어 있을 뿐이다. 각각의 남성 번호를 들고서 리스트에서 1위부터 순서대로 찾기 시작하면 O(n) 탐색을 2번 시행해야하므로 O(n) 시간으로 해결할 수 있다. 이것은 비효율적이다. 전체 알고리즘을 시작하기에 앞서, 여성 n명의 선호도 리스트를 쭉 탐색하면서 남성 번호를 입력했을때 해당하는 남성의 선호도(-> 남성에 대한 여성들의 선호도)를 곧장 알 수 있게끔 하는 데이터 구조를 하나 만드는 것이 좋다. 이를 역 선호도 리스트라고 부르자. 미리 만들어둔 데이터 덕분에 나중엔 O(1) 시간 안에 남성 두 명을 비교할 수 있게 된다. 참고로 이렇게 데이터를 미리 만드는 시간도 O( n^2 )이므로 전체 알고리즘의 order는 변하지 않는다.

O( n^2 )에 해결할 수 있다!

2. 관찰

이 알고리즘은 여성 기준에서 봤을때, 본인이 한 번 약혼에 성공하면 다시는 싱글로 돌아갈 수 없게 된다. 파혼과 동시에 다시 약혼할 남성이 정해지기 때문이다.

한편, 남성 기준에서는 전체 결혼 시스템의 안정성을 망가뜨리지 않는 조건 상에서 본인이 가장 좋아하는 여성과 결혼할 수 있게 된다. 모든 프로포즈 상황에서 남성은 자신이 아직 프로포즈하지 않은 여성 중에 가장 선호하는 여성에게 프로포즈하기 때문이다.

지도 교수와 학생을 이 알고리즘으로 매칭시키게 되면 안정적으로 결ㅎ....읍으브ㅡㅡ브븡ㅂ읍...

매칭시키게 되면 어느 쪽이 위 알고리즘의 남성 역할을 하게 되느냐에 따라 매칭 결과가 달라지게 된다 !!!

과연 누가 더 선호했을까나...

3. 안정적인 결혼 검증 알고리즘

무튼 해답이 여러 가지로 나올 수 있는 알고리즘이다. 따라서 정확한 답을 냈는가 검증이 필요하다. 참고로 얼마 전 과제로 이걸 냈었고 나는 틀렸다 ㅎㅎ 수정본을 포스팅하려고 이 글을 쓰기 시작했다.

알고리즘의 핵심은 간단하다. 불안정한 커플이 있는지 확인하는 것이다. 저~기 위에서 불안정한 커플의 정의를 써놨다. 저런 커플이 있는지 확인하면 된다.

 - 임의의 커플 한 쌍(남성 m, 여성 w)을 데려온다.

 - 남성 m의 선호도 리스트를 참고하여 현재 배우자(아내)보다 선호하는 여성들을 데려온다.

 - 이 여성들 모두에 대해 현재 배우자(남편)보다 남성 m을 더 좋아하는지 확인한다.

 - 만약 확인된다면 불안정한 커플이 발견된 것이다.

 - 이 과정을 모든 커플에 대해 검사한다.

남녀 n명씩 알고리즘에 참여했었으므로 커플도 n 쌍이다. 모든 커플에 대해 한 번씩 확인해야하므로 적어도 O(n) 탐색 시간이 소요된다. 임의의 한 커플에 대해 남성의 선호 여성들을 모두 검사해야하므로 O(n) 시간이 필요하다. 따라서 O( n^2 ) 시간이 소요된다.

마찬가지로 구현 상에서는 여성이 두 남성을 놓고서 어느 남성을 더 좋아하는지 O(1) 시간 안에 검사할 수 있어야한다. 이를 위해 미리 두 가지 데이터 구조를 준비해야한다. 첫 번째는 여성 번호를 입력하면 곧장 남편을 알 수 있게 만드는 리스트가 필요하다. 이게 없다면 결혼 결과 리스트에서 O(n) 시간을 들여 탐색해야한다. 두 번째는 임의의 여성에 대해 남성들의 선호도를 곧장 알 수 있게 만드는 리스트가 필요하다. 이는 실제 안정적인 결혼을 만들 때 썼던 여성 n명에 대한 역 선호도 리스트와 동일하다. 앞서 말한 알고리즘 시행과는 별도로 미리 준비해야하는 것이고 O( n^2 ) 시간 안에 준비된다.

따라서 전체 알고리즘은 O( n^2 ) 시간 안에 해결된다.

---

참고로 소스코드는 github에 공개해뒀으며 링크는 여기 (Link) 있다. 코드는 길지 않지만 m, w 등등 따지다보니 생각보다 디버깅이 힘들었다.