매칭은 어떻게 구현할까? (안정 결혼 문제, 매칭 알고리즘)

들어가며

 

알고리즘을 통해서어떻게 매칭을 구현할 수 있을까? 남자와 여자 각각 원하는 상대방의 리스트를 가지고 있다고 하자. 이를 어떻게 매칭시켜야 가장 뒷말이 안 나오는 매칭을 구현할 수 있을까? 이러한 문제를 안정 결혼 문제(Stable Marriage Problem)이라고 부른다.

 

SMP의 목표는 모든 매칭이 안정적이게끔 하는 것이다. 여기서 '안정적'이라는 것은 어떤 두 사람이 현재의 매칭 상태보다 서로 더 선호하는 경우가 없다는 것을 의미한다. 구체적으로는 어떤 남성 M과 여성 W가 서로의 현재 파트너보다 더 선호하는 경우가 없는 상태를 의미한다. 즉, 모든 구성원들이 현재의 매칭 상태를 바꾸고 싶어하지 않도록 만드는 것이 목표다.

 

백준 문제 풀이 사이트에서 해당 문제에 대한 레퍼런스를 가져오면 다음과 같다. 영문으로 문제가 쓰여있다.

• 백준 : https://www.acmicpc.net/problem/3761

이러한 문제를 해결하기 위해 발명된 알고리즘이 있다. 그것은 바로 gale-shapley 알고리즘이다. 이번 포스팅에서는 남자 여자 각각 N 명일 때 수행할 수 있는 gale-shapley 알고리즘과 남자와 여자가 N명 M명으로 인원 수가 다를 때 사용할 수 있는 매칭 알고리즘인 Hospital Resident 알고리즘에 대해서 살펴보고자 한다.

 

본론

Stable Marriage Problem

1962년에 이러한 안정 결혼 문제를 해결한 사람이 등장한다. 그 두 사람은 바로 데이비드 게일과 로이드 샤플리이다. 컴퓨터와 수학을 전공한 이 둘은 이러한 알고리즘이 항상 최적해를 보장한다는 것을 증명하였다.

 

위키피디아에 따르면 알고리즘은 아래와 같다.

algorithm stable_matching is
    Initialize m ∈ M and w ∈ W to free
    while ∃ free man m who has a woman w to propose to do
        w := first woman on m's list to whom m has not yet proposed
        if ∃ some pair (m', w) then
            if w prefers m to m' then
                m' becomes free
                (m, w) become engaged
            end if
        else
            (m, w) become engaged
        end if
    repeat

 

위 코드의 내용을 파이썬으로 구현하면 다음과 같다.

def stable_matching(men_preferences, women_preferences):
    free_men = list(men_preferences.keys())
    engaged_pairs = {}
    women_engaged_to = {woman: None for woman in women_preferences}

    proposals = {man: list(women) for man, women in men_preferences.items()}

    while free_men:
        m = free_men[0] 
        if proposals[m]:
            w = proposals[m].pop(0)
            
            if women_engaged_to[w] is None:
                engaged_pairs[m] = w
                women_engaged_to[w] = m
                free_men.pop(0)
            else:
                m_prime = women_engaged_to[w]
                if women_preferences[w].index(m) < women_preferences[w].index(m_prime):
                    free_men.append(m_prime)
                    engaged_pairs[m] = w
                    women_engaged_to[w] = m
                    free_men.pop(0)
        else:
            free_men.pop(0)
    
    return engaged_pairs

men_preferences = {
    'A': ['X', 'Y', 'Z'],
    'B': ['Y', 'X', 'Z'],
    'C': ['X', 'Z', 'Y']
}

women_preferences = {
    'X': ['B', 'A', 'C'],
    'Y': ['A', 'B', 'C'],
    'Z': ['A', 'B', 'C']
}

print(stable_matching(men_preferences, women_preferences))

 

Hospital-Resident problem

Gale-Shapley 알고리즘은 이상적인 매칭을 구현해주는 알고리즘이지만, 제약 조건이 꽤 많다. 남자와 여자의 수가 같아야 하고 선호도의 리스트도 같아야 한다는 조건이 있다.

 

만약, 그렇지 않다면 어떻게 해결할 수 있을까? 이러한 문제를 hospital-resident problem이라고 부르며 college admissions problem이라고 부르기도 한다. 이름만 봐도 대충 왜 그런 것인 지 알 수 있을 것 같다. 이는 대학 병원에서나 대학교에서 한 명 이상의 사람을 받을 수 있기 때문에 이렇게 불리게 된다.

 

만약 남자와 여자를 매칭시켜주는 소프트웨어를 개발한다고 하자. 남자와 여자의 성비를 맞출 수 있을까? 일반적으로는 다를 것이다. 그럴 때 사용할 수 있는 알고리즘이 바로 Gale-Shapley 알고리즘을 개량한 Hospital-Resident 알고리즘이다. 이 알고리즘에 대해서는 이미 구현되어 있는 파이썬 라이브러리를 참고하도록 하자.

• PyPI : https://pypi.org/project/matching/

matching

 

위 라이브러리를 살펴보면 GaleShapley와 HospitalResident 메서드가 있는 것을 확인할 수 있다. 위 레퍼런스에서 확인할 수 있듯이 파이썬의 딕셔너리 타입으로 남자와 여자의 선호도 리스트를 전달하면 그에 맞게 매칭 결과를 반환해주는 메서드이다. 다음과 같이 사용할 수 있다.

 

from matching.games import HospitalResident
resident_prefs = {"R1": ["H1", "H2"], "R2": ["H2", "H1"]}
hospital_prefs = {"H1": ["R1", "R2"], "H2": ["R2", "R1"]}
capacities = {"H1": 1, "H2": 1}
game = HospitalResident.create_from_dictionaries(resident_prefs, hospital_prefs, capacities)
matching = game.solve()
print(matching)

 

HospitalResident 알고리즘은 대학 병원이나 대학교처럼 여러 사람들을 받을 수 있게 고안되어있기 때문에, 성비가 맞지 않는 상황에서 남자와 여자를 1대1로 매칭시켜주기 위해서는 capacities의 값을 1로 줘서 1대1 매칭을 구현할 수 있다.

 

마치며

안정 결혼 문제 백준 풀이 관련해서 solve.ac 기준으로 플레티넘 1 문제들의 풀이를 올려놨으니 참고가 필요한 사람들은 참고하면 좋을 것 같다.

안정 결혼 문제

추가로, 원래 골드1 에서 도통 점수가 오를 생각을 안했다가, 이번에 Gale-Shapley 문제를 많이 풀었더니 플레티넘이 되었다 :)

 

참고

감사합니다.