-
The Short-Side Advantage in Random Matching Markets
이 글은 L. Cai와 C. Thomas의 논문 The Short-Side Advantage in Random Matching Markets 의 결과를 간략하게 정리한 것이다. 1. Introduction Stable Matching Problem은 남-여 간의 짝 매칭, 의사와 병원간의 매칭, 학생과 지도교수 간의 매칭 등 여러 상황에서 응용될 수 있는 문제로 다음과 같은 상황을 다룬다. $n$ 명의 의사 $\mathcal{D} = {d_1, d_2, \cdots, d_n}$ 와 $m$ 개의 병원 $\mathcal{H} = {h_1, h_2, \cdots, h_m}$ 이 있다. 각각의 의사는 병원에 대한 선호하는 순서($\prec_d$)가 존재하고, 각각의...
-
랜덤 올바르게 사용하기
서론 프로그램을 작성할 때 랜덤한 요소는 많이 들어갑니다. 어떤 공간을 탐색할 때 무작위로 탐색을 하기도 하고, 프로그램의 비밀 키를 만들거나 게임을 만들 때 카드 덱을 섞을 때 등, 랜덤이 프로그램에 사용되는 곳은 굉장히 많습니다. 하지만 이 랜덤은 자주 잘못 사용되고는 합니다. 랜덤을 올바르게 사용하는 방법에 대해 알아보려고 합니다. 랜덤이란? 랜덤이란 특정한 패턴이 없다는 것을 말합니다. 즉, 어떤 규칙에 의해 생성되지 않고 다른 변수와 독립적으로 만들어진 결과를 랜덤한 결과라고 합니다. 과연 완벽한 좋은 랜덤을 만들 수...