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$)가 존재하고, 각각의 병원은 의사에 대한 선호하는 순서($\prec.. Computational Complexity Classes 최근 https://github.com/koosaga/project-hardness 의 스터디에 참여하고 있다. 해당 스터디에서 공부한 내용을 아주 간략히 (주로 informal 하다.) 간혹 정리해볼 예정. P와 NP P와 FP $\mathbb{P}$는 다항 시간(입력 $x$의 크기에 대해 다항식 scale로 bound 됨을 의미)에 풀리는 문제들의 class이다. 유의 사항: 정수 $n$은 $\log_2 n$ 개의 비트로 표현할 수 있으므로 $n$을 입력으로 줄 때 입력의 크기는 $\log_2 n$ 이다. (흔히들 Subset Sum 등을 $\mathbb{P}$라 생각하면서 하는 오해...) $\mathbb{FP}$는 다항 시간에 계산 가능한 함수들의 class이다. 어떤 계산 모델을 가정할 것인가?.. Redis는 어떻게 key를 expire 하는가? Redis에서는 key에 timeout을 설정할 수 있다. 이 경우, timeout이 지난 key는 만료(expire) 되어 redis에서 삭제된다. 이전 회사에 다니던 시절에 Redis로 key에 timeout을 걸어줘야 하는 작업을 하면서 이 기능이 어떤 원리로 동작하는지에 대해 의문을 품고 찾아봤던 일이 있었다. 이와 관련하여 지금은 조금 여유가 생겨 간략히 글을 남겨본다. Key가 만료되었는지 확인하고, 삭제할 수 있는 가장 간단한 전략으로는 다음의 두 가지를 생각해 볼 수 있다: eager way: 주기적으로 전체 key들을 살펴보며 timeout에 도달했는지 체크해보고, 도달한 경우 key를 삭제한다. lazy way: 어떠한 key에 대한 접근이 이루어지는 시점에 timeout에 도달했는지 .. 이전 1 2 3 4 5 6 7 8 ··· 22 다음