| [ QuizWit ] in KIDS 글 쓴 이(By): novio (노뵤) 날 짜 (Date): 2007년 9월 7일 금요일 오전 06시 15분 58초 제 목(Title): Stable Marriage 문제 N명의 남자와 N명의 여자가 있는데 얘네들을 짝을 지워서 N쌍의 커플을 만들어야 합니다. 모든 사람들은 N명의 이성에 대해 자기가 제일 좋아하는 사람부터 제일 싫어하는 사람까지 마음 속으로 랭킹을 갖고 있습니다. 어떤 남자가 3번 여자를 제일 좋아하고 그 다음 4번, 1번, 2번 순으로 좋아 한다면 (3,4,1,2)란 랭킹을 갖고 있는 거죠. 짝을 지을 때의 규칙은 나중에 불륜 커플이 나와서는 안 된다는 겁니다. 불륜은 고수와 박경림을 그리고 이혁재와 전지현을 커플로 맺어줬는데 원래 고수는 박경림보다 전지현을 더 좋아했고 전지현도 이혁재보다 고수를 더 좋아했다면 발생하게 됩니다. 불륜이 안 생기게 N쌍의 커플을 만들 수 있는 알고리즘 중에 Traditional Marriage 방식이 있습니다. 남자는 자기의 선호도 랭킹 중에 1위인 여자한테 찾아갑니다. 여자는 자기를 찾아온 남자들 중에서 자기가 가장 좋아하는 남자한테는 Maybe라고 말하고 다음날 또 찾아오라고 얘기하고, 나머지 남자들한테는 딱지를 놓습니다. Maybe를 받은 남자는 다음날 또 그 여자를 찾아가고 나머지 남자들은 자기 랭킹 리스트에서 그 여자를 지운 다음에 그 다음 랭킹이 높은 여자를 찾아가는 과정이 반복됩니다. 이런 방식으로 커플을 맺으면 남자에게 유리할까요 여자에게 유리할까요? (남자 입장에서는 아무에게도 불륜이 안 생기면서 자기하고 연결될 수 있는 여자 중에서 제일 랭킹이 높은 여자랑 연결이 되는게 최적이죠) |