안정 결혼 문제(stable matching, stable marriage, gale shapley algorithm)

1. 어떻게 남녀를 맺어줘야 행복하게 살수 있을까? 결혼중매업자인 대혁에게는 200명의 고객이 있다. 100명은 남자, 100명은 여자이다. 여자 고객은 각자 남자 고객 100명을 대상으로 선호도에 따라 순위를 매겨 대혁에게 제출한다. 각자 명단의 맨 위에는 완벽한 이상형이 있고, 아래로 갈수록 호감도가 떨어져 맨 아래에는 최악의 기피남이 있다. 남자 고객 100명도 마찬가지로 여자 고객 100명을 대상으로 순위를 매겨 제출한다 대혁은 이 선호도 조사 결과를 바탕으로 남녀 고객을 맺어줘야한다. 어떻게 맺어줘야 이들이 결혼에 골인하고 가정을 이루고 오래오래 행복하게 살 수 있을까? 당연한 말이지만, 일부는 자신의 제1지망과 맺어지지 못한다.  같은 남자를 여러 여자가 제1지망으로 찍었다면 누군가는 고배를 ..

• format_list_bulleted 고급 알고리즘
• · 2024. 7. 31.
• textsms

핵심 알고리즘 파악하기

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 programmers.co.kr 괄호가 바르게 짝지어졌다는 것은 ‘(‘ 문자로 열렸으면 반드시 짝지어서 ‘)’문자로 닫혀야 한다는 뜻입니다. 예를 들어 ‘()()’ 또는 ‘(())()’는 올바른 괄호입니다. ‘)()(‘ 또는 ‘(()(‘는 올바르지 않은 괄호입니다. ‘(‘ 또는 ‘)’로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올..

• format_list_bulleted 알고리즘 일반
• · 2022. 1. 12.
• textsms