RSS 리더를 읽다가 10여년 전 배웠던 알고리즘을 소개하는 글을 봤습니다. 당시 이 알고리즘을 배우고 나서, 혼자 마음 속으로 명명하기로 Happy Marriage Algorithm 이라 했었는데, 실제로 이 문제의 이름은 Stable Marriage Problem (SMP) 이더군요.

http://en.wikipedia.org/wiki/Stable_marriage_problem

문제는 간단합니다.

남자와 여자가 같은 수가 있으며, 모든 남성과 여성은 모두 이성에 대한 선호도를 Linear Order 로 가지고 있다고 가정합니다. 이 때 남자와 여자간에 일대일 대응을 주었습니다. 만약 서로 대응되지 않은 어떤 남성과 어떤 여성이 서로에 대한 선호도가 각자의 대응된 이성보다 높게 되면, 이 상태를 불안정하다고 합시다.

주어진 선호도에 따라서 모두가 안정되게 대응시킬 수 있을까요?

해결 방법은 다음의 링크를 눌러서 글을 읽어 보시길 바랍니다.

http://intothereign.tistory.com/194

이 알고리즘의 단점은 알고리즘 종료 시점을 미리 알 수 없어서 Time complexty 를 계산할 수 없다는 점입니다. 하지만 여러가지 형태의 다대다 대응 모델로 쉽게 확장 할 수 있는 장점이 있습니다.

그나저나 이런 알고리즘으로 모두가 행복해 질 수 있을까요?

'Thoughts > Math' 카테고리의 다른 글

재밌는 시외버스 가격  (3) 2009.08.26
적분 문제  (4) 2009.06.25
Stable Marriage Problem  (13) 2009.05.05
2014년 국제 수학자 대회 (ICM) 서울 유치  (0) 2009.04.23
정수일까? 아닐까?  (0) 2009.02.12
Ramanujan's infinitely nested radicals problem  (2) 2009.01.17
  1. Favicon of https://gguro.com (gguro) 2009.05.05 20:57 신고

    뭔가 좀 생각해보려고 했는데,
    왜 여자가 남자보다 불리한지에 대해서 말이지.
    아, 생각해보기가 귀찮아졌어 ㅠㅠ

    • Favicon of https://gguro.com (gguro) 2009.05.07 17:17 신고

      역시 적극적인 쪽이 이익인 것인가?

    • Favicon of https://blog.hshin.info Ens 2009.05.07 19:24 신고

      주어진 선호대에 대해 안정된 대응이 여러 개일 수 있잖아? (물론 단 한 개일 수도 있지만..)
      이럴 경우에 그 여러가지 안정된 대응 중에서 이 알고리즘으로 찾은 대응은 개별 여성으로 볼 때는 최악을 선택한 것이고, 개별 남성은 최선을 선택하게 되는 것인데..

      그 이유는 여자는 가만히 앉아서 나에게 대시해 오는 남성을 기다리면서 시간이 지나면서 대응되는 남성의 선호도가 높아지는 반면에, 남자는 자신이 가장 선호하는 여성부터 아래로 내려가기 때문에 점점 대응하려는 여성의 선호도는 점점 내려가게 된다. 그렇기 때문에 알고리즘이 종료될 때 남성은 upper bound 에, 여성은 lower bound 에서 선택이 되고, 각각 최선과 최악을 선택하게 된다는 이야기..

      근데 이 문제보다 그냥 남성 여성 구별 없이 2n 명의 학생이 룸메이트를 구하는 문제가 더 재밌는 것 같다. 어떻게 하면 될까?

    • Favicon of https://blog.hshin.info Ens 2009.05.07 19:28 신고

      실제에서는 환경이 다르고, 중간에 선호도가 변경되는 등 다양한 변수가 존재하지만..
      적극적인 것이 수동적인 것 보다는 이득을 취할 가능성이 높다는 거지..
      실제로 대학이나 기업에서 학생을 선발할 때, 수준 높은 학생이 지원하기를 기다리는 것 보다 수준 높은 학생을 찾아 유치하려는 노력이 필요하다는 정도에서 적용해 볼 수 있을 것 같은데..

    • 모아 2009.05.08 05:35

      이 알고리즘은 KAIST 전산과에서 학생, 교수 짝지을때 사용했다는.
      학생이 남자, 교수가 여자.

    • Favicon of https://blog.hshin.info Ens 2009.05.10 04:42 신고

      내가 알기로는 교수가 남자, 학생이 여자였다는 것 같던데.. 아닌가?

  2. 병철 2009.05.08 14:57

    SMP가 Time Complexity를 구할 수 없었던가? Worst Case Analysis가 가능했던거 같은데...
    아마도 모든 남자들의 선호 순위가 동일하게 매겨지면 Worst Case가 되지 않을까?

    즉, 매 턴마다 모든 남자가 한명의 여자에게 몰리고, 여자는 그중 누구를 고르든
    한 턴에서 하나의 커플만 만들어지니까... 그러면 Worst Case의 Time Complexity는
    O(n^2)가 되는게 아닌가?
    (한 턴의 처리는 여자쪽에서 남자들 중 선호도 높은 한명을 골라내니 O(n) )

    • Favicon of https://blog.hshin.info Ens 2009.05.10 04:40 신고

      이게 worst case 가 아닌 것 같은데..
      자세한 건 여행 끝나고 한 번 생각해 보자..

    • 병철 2009.05.14 16:11

      뭐 나도 사천에서 더위 먹은채로 쓴 거라
      확신이 서지는 않는군. @_@;

      대체로 이쪽 문제는 Graph 문제로 변형을 해서 풀어보면 답이 나오는게 꽤 있을텐데...

      (Happy Marriage하고 비슷한듯 다른 문제가 Bipratite Graph에서의 Maximum Matching이지)

      역시 한동안 연구를 안했더니 머리가 굳는군... 큰일이다.

  3. 병철 2009.05.08 15:03

    그리고 위에 SMP의 위키피디아 내용 아래에 Similar Problem에 보면
    Stable Roommate Problem 이라는 것도 있군. ㅎㅎ;;;

    • Favicon of https://blog.hshin.info Ens 2009.05.10 04:39 신고

      그렇긴 한데.. 이 경우에 좀더 복잡해지는 것 같던데.. ㅎㅎ

  4. 승리양 2009.06.27 02:20

    결혼이야기구나 하고 들어왔는데...
    역시 난 문제만 읽고 나서 바로 귀찮아졌어.
    가끔 생각하지만, 난 아무래도 다른 대학에 갔었어야 했나봐~~~ㅋ

    • Favicon of https://blog.hshin.info Ens 2009.06.27 07:04 신고

      이 문제는 뭐.. 좀 수학보다는 전산학 오리엔티드 된 문제인지라..
      그나더나 다른 대학이라면, 구체적으로 어디를 생각하는데가 있어?
      다른 대학을 갔어도 잘 했을 것 같기도 하고..

+ Recent posts