SMP (1) 썸네일형 리스트형 152. Stable Marriage Problem 안정적인 결혼 문제(Stable Marriage Problem, SMP)는 크기가 동일한 두 집합에서 안정적인 매칭(Stable Matching)을 찾는 문제이다. 두 집합 간의 안정적인 매칭이라는 것은 다음과 같다. 각 집합의 원소는 상대 집합의 원소들에 대한 서로 다른 선호도를 가진다. 첫 번째 집합과 두 번째 집합의 원소가 일대일로 매칭되어 있다. 첫 번째 집합에 속한 원소 $A$, $B$가 두 번째 집합에 속한 원소 $C$, $D$와 각각 매칭되어 있을 때 $A$가 $C$보다 $D$를 선호하면서 $D$가 $B$보다 $A$를 선호하는 경우는 존재하지 않는다. 세 번째 조건을 다시 설명하면 서로 매칭되지 않은 두 원소 모두가 상대 원소를 자신과 매칭된 원소보다 더 선호하는 경우가 존재하지 않는다는 것.. 이전 1 다음
