백준

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

들어가며 평소에 백준 사이트에서 PS 문제를 푸는 것을 좋아한다. 알고리즘을 공부하는 것 자체만으로도 재미있고, 코딩 테스트를 언제든 준비할 수 있게끔 녹슬지 않게 실력을 가꾸기 위해서이다. 직접 백준 문제를 풀면서 파이썬을 통해 백준 문제를 풀 때 알아두면 좋은 것들을 정리하려고 한다. 이번 포스팅에서 다루는 것은 파이썬으로 백준 문제를 풀 때에 꼭 알아두어야 맞왜틀( 맞았는데 왜 틀리지 )을 방지할 수 있을만한 내용들이다. 본론시간복잡도 계산알고리즘을 푼다라고 하면 가장 기본적인 것은 시간복잡도 계산이다. 알고리즘에는 다양한 것들이 있지만, 우리가 기본적으로 사용하는 알고리즘의 시간 복잡도를 알고 있다고 가정하자. ( 예를 들어 이진 탐색의 시간 복잡도가 O(logN)이라는 것을 알고 있다 ) 그리고..