파이썬

들어가며 알고리즘을 통해서어떻게 매칭을 구현할 수 있을까? 남자와 여자 각각 원하는 상대방의 리스트를 가지고 있다고 하자. 이를 어떻게 매칭시켜야 가장 뒷말이 안 나오는 매칭을 구현할 수 있을까? 이러한 문제를 안정 결혼 문제(Stable Marriage Problem)이라고 부른다. SMP의 목표는 모든 매칭이 안정적이게끔 하는 것이다. 여기서 '안정적'이라는 것은 어떤 두 사람이 현재의 매칭 상태보다 서로 더 선호하는 경우가 없다는 것을 의미한다. 구체적으로는 어떤 남성 M과 여성 W가 서로의 현재 파트너보다 더 선호하는 경우가 없는 상태를 의미한다. 즉, 모든 구성원들이 현재의 매칭 상태를 바꾸고 싶어하지 않도록 만드는 것이 목표다. 백준 문제 풀이 사이트에서 해당 문제에 대한 레퍼런스를 가져오면 ..

문제해설gale-shapley 알고리즘을 기반으로 하고 있으나 쌍이 주어지지 않는다. 중요한 포인트는 다음 부분이다. 즉 선호도 테스트 케이스가 다음과 같이 주어지면51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 5 카이스트 학생들의 선호도는 다음과 같이 나와야 한다. 5 4 3 2 15 4 1 3 21 5 2 4 31 2 3 5 41 2 3 4 5 따라서, 저 조건에 맞에 카이스트 학생들의 선호도를 만들어준 후 gale-shapley 알고리즘을 사용하면 풀 수 있다. 필자는 다음과 같이 구현했다.for i in range(1, n+1): temp = [i] for dist in range(1,n): for j in range(n, 0, -1): ..

문제해설gale-shapley 알고리즘을 통해 풀이할 수 있다. 파이썬 코드는 아래와 같다.코드import sysinput = sys.stdin.readlinen = int(input())men = input().split()women = input().split()men_prefs, women_prefs = {}, {}for pivot in (men_prefs, women_prefs): for _ in range(n): people = input().split() pivot[people[0]] = people[1:]def stable_marriage(men_prefs, women_prefs): men = list(men_prefs.keys()) women = l..

문제해설남자와 여자의 수가 n명으로 일치하고, 서로의 선호도를 리스트로 받기 때문에 gale-shapley 알고리즘으로 풀이할 수 있다.코드import sysinput = sys.stdin.readlinet = int(input())def stable_marriage(men_preferences, women_preferences): n = len(men_preferences) free_men = list(range(n)) women_partners = [None] * n men_next_proposal = [0] * n men_partners = [None] * n women_rankings = [] for wp in women_preferences: ..

문제안정 결혼 문제를 푸는 알고리즘을 구현하는 것이다. 안정 결혼 문제(Stable Marriage Problem)은 예전부터 제시됐던 문제이다. 남자와 여자가 각각 n명으로 같은 수의 집합이 주어지고, 서로 원하는 상대방에 대한 선호도를 리스트로 가지고 있다. 이를 해결하기 위한 도전은 안정 매칭(Stable Matching)을 모두 구현해야 한다. 안정 매칭이란 일대일로 남자와 여자를 매칭하는데, f ∈ F가 현재 파트너보다 m ∈ M을 선호하고 m이 현재 파트너보다 f를 선호하는 쌍(m, f)이 없는 경우 매칭을 안정적이라고 합니다. 다른 안정된 결혼 B가 없는 경우, 어떤 남성이든 A에 배정된 여성보다 더 선호하는 여성과 짝을 이루는 안정된 결혼 A를 남성 최적이라고 합니다. 선호하는 남성과 여성..