정글의 팀 결성 방법

정글의 최종 프로젝트를 앞두고, 약 5주간 함께 할 팀을 결성해야 했다.

 

정글의 팀 결성 방법은 매우 흥미롭다. 일반적으로, 적어도 내가 겪은 바로는 마음 맞는 사람들끼리 비공식적으로 팀을 구성한 후, 리더를 선출하고 최종적으로 팀 리스트를 제출하는 방식이었다. 그러나 정글에서는 팀 매칭 알고리즘이 존재하고, 이를 통해 팀이 결성된다. 이를 통해 개개인의 만족도, 공정성을 최대화 할 수 있다. (사실 잘 모르겠다)

 

예를 들어, 먼저 리더 역할에 지원한 사람들 중 N명을 선발한다. 이후, 이 N명의 리더와 나머지 멤버들 간의 선호도를 기반으로 알고리즘을 실행해 팀을 결성하는 방식이다.

 

정글에선 팀 매칭 알고리즘으로 hospital-resident matching 방식을 사용한다. 이 알고리즘은 stable marriage matching 방식의 확장으로, stable marriage 이 일대일 매칭을 다룬다면, hospital-resident 은 다대일 매칭을 다룬다고 할 수 있다. 이 두 매칭 방식을 구현하기 위해 내부적으로 Gale-Shapley 알고리즘이 활용된다. 다만, 일대일 매칭과 다대일 매칭의 특성에 따라 알고리즘의 로직이 약간씩 달라진다.

 

hospital-resident matching 방식에서 사용되는 Gale-Shapley 알고리즘에 대해 설명하자면, 멤버가 자신의 선호도에 따라 리더에게 프로포즈를 보내는 방식으로 작동한다. 리더는 자신의 용량(capacity) 내에서 선호도가 높은 멤버를 임시로 수락하고, 나머지는 거절한다. 거절된 멤버는 다음 선호 순위의 리더에게 다시 프로포즈하며, 리더는 새로운 프로포즈와 기존 수락 상태를 비교해 선호도에 따라 팀 구성을 조정한다. 이 과정을 반복해 모든 멤버가 안정적으로 매칭될 때까지 진행한다.

 

요약하면 다음과 같다:

1. 각 리더는 수용 가능한 인원의 최대치(capacity)를 가지고 있다.

2. 멤버들은 자신의 리더 선호도 순위를 1위부터 마지막까지 나열한다.

3. 리더들은 자신의 멤버 선호도 순위를 1위부터 마지막까지 나열한다.

4. 멤버는 자신의 선호도 순으로 리더에게 프로포즈를 보낸다.

5. 리더는 받은 프로포즈 중에서 자신이 선호하는 멤버를 우선적으로 선택한다. 이때, 리더의 용량을 초과하는 프로포즈가 있다면, 선호도가 낮은 멤버부터 거절한다.

6. 거절된 멤버들은 자신의 다음 선호 순위 리더에게 다시 프로포즈를 보낸다.

7. 리더는 새롭게 받은 프로포즈와 기존에 수락했던 멤버를 비교하여, 여전히 선호도가 높은 멤버를 유지하고, 낮은 멤버를 제외한다.

8. 이 과정을 모든 멤버가 매칭되거나 선택할 리더가 없을 때까지 반복하며, 최종적으로 안정적인 매칭 상태를 만든다.

 

안정적으로 매칭된다는 것의 의미는, 매칭된 멤버와 리더 간에 더 나은 선택으로 인해 매칭이 깨질 가능성이 없다는 것을 뜻한다.

 

다음은 이를 python 으로 구현한 코드이다.

def member_proposing_matching(leaders, members):
    matches = {l: [] for l in leaders}  # 매칭 결과
    free_members = list(members.keys())  # 소속되지 않은 멤버 리스트

    while free_members:
        m = free_members.pop(0)
        for l in members[m]:
            if len(matches[l]) < leaders[l]["capacity"]:  # 리더가 수용 가능한 경우
                matches[l].append(m)
                break
            else:  # 수용 불가능한 경우
                lowest_ranked = max(matches[l], key=lambda x: leaders[l]["preferences"].index(x))
                if leaders[l]["preferences"].index(m) < leaders[l]["preferences"].index(lowest_ranked):
                    matches[l].remove(lowest_ranked)
                    matches[l].append(m)
                    free_members.append(lowest_ranked)
                    break
    return matches
    
leaders = {
    "L1": {"capacity": 2, "preferences": ["M1", "M2", "M3", "M4", "M5", "M6"]},
    "L2": {"capacity": 2, "preferences": ["M3", "M1", "M5", "M2", "M6", "M4"]},
    "L3": {"capacity": 2, "preferences": ["M6", "M4", "M5", "M3", "M2", "M1"]},
}

members = {
    "M1": ["L3", "L2", "L1"], # L3 -> L2 -> L1 순으로 선호
    "M2": ["L1", "L3", "L2"],
    "M3": ["L2", "L1", "L3"],
    "M4": ["L3", "L1", "L2"],
    "M5": ["L2", "L3", "L1"],
    "M6": ["L1", "L3", "L2"],
}

member_proposing_result = member_proposing_matching(leaders, members)
print(member_proposing_result)

 

좀 더 자세한 시나리오로 들어가보자.

 

정글의 총 인원이 28명이고, 리더가 6명, 멤버가 22명이라고 가정하자. 이때, 리더의 최대 수용 인원은 전체 멤버 수를 기준으로 (최대 - 최소 ≤ 1) 조건을 만족하도록 랜덤하게 설정된다. 즉, 랜덤하게 2명의 리더는 수용 인원이 4명, 나머지 4명의 리더는 수용 인원이 5명이 되는 셈이다.

 

리더는 멤버를 1위부터 22위까지 선호도 순위로 평가하고, 멤버는 리더를 1위부터 6위까지 선호도 순위로 정한다. 이후, 멤버들은 자신의 선호도에 따라 리더에게 프로포즈를 보낸다. 리더는 수용 인원(capacity)을 기준으로 프로포즈를 받은 멤버 중 선호도 순위가 높은 멤버를 임시로 선택하고, 나머지는 거절한다. 거절당한 멤버들은 자신의 다음 선호 순위에 있는 리더에게 프로포즈를 보내며, 리더는 기존 선택과 새로운 프로포즈를 비교해 더 선호하는 멤버를 다시 선택한다.

 

이를 안정적인 매칭 상태가 될 때 까지 계속 반복한다.

 

아래 링크는 팀 매칭을 시뮬레이션할 수 있도록 JavaScript로 구현한 사이트이다.

https://stablematch.hjyoon.me/

카이스트 정글 팀 형성 시뮬레이터 v2024.12

 

서버와의 상호작용이 없기 때문에 입력한 리더와 멤버 정보는 로컬에 저장해야 한다. 이를 위해 import / export 기능을 활용할 수 있다.

 

 

소스코드

https://github.com/hjyoon/jungle-team-simulator