들어가며 알고리즘을 통해서어떻게 매칭을 구현할 수 있을까? 남자와 여자 각각 원하는 상대방의 리스트를 가지고 있다고 하자. 이를 어떻게 매칭시켜야 가장 뒷말이 안 나오는 매칭을 구현할 수 있을까? 이러한 문제를 안정 결혼 문제(Stable Marriage Problem)이라고 부른다. SMP의 목표는 모든 매칭이 안정적이게끔 하는 것이다. 여기서 '안정적'이라는 것은 어떤 두 사람이 현재의 매칭 상태보다 서로 더 선호하는 경우가 없다는 것을 의미한다. 구체적으로는 어떤 남성 M과 여성 W가 서로의 현재 파트너보다 더 선호하는 경우가 없는 상태를 의미한다. 즉, 모든 구성원들이 현재의 매칭 상태를 바꾸고 싶어하지 않도록 만드는 것이 목표다. 백준 문제 풀이 사이트에서 해당 문제에 대한 레퍼런스를 가져오면 ..
알고리즘
들어가며 평소에 백준 사이트에서 PS 문제를 푸는 것을 좋아한다. 알고리즘을 공부하는 것 자체만으로도 재미있고, 코딩 테스트를 언제든 준비할 수 있게끔 녹슬지 않게 실력을 가꾸기 위해서이다. 직접 백준 문제를 풀면서 파이썬을 통해 백준 문제를 풀 때 알아두면 좋은 것들을 정리하려고 한다. 이번 포스팅에서 다루는 것은 파이썬으로 백준 문제를 풀 때에 꼭 알아두어야 맞왜틀( 맞았는데 왜 틀리지 )을 방지할 수 있을만한 내용들이다. 본론시간복잡도 계산알고리즘을 푼다라고 하면 가장 기본적인 것은 시간복잡도 계산이다. 알고리즘에는 다양한 것들이 있지만, 우리가 기본적으로 사용하는 알고리즘의 시간 복잡도를 알고 있다고 가정하자. ( 예를 들어 이진 탐색의 시간 복잡도가 O(logN)이라는 것을 알고 있다 ) 그리고..