삶을 사는 지혜

비서 문제(Secretary Problem)

컴퓨터 공학을 전공하면서 알고리즘 문제 중 가장 인상 깊었던 문제를 하나 꼽자면 비서 문제(Secretary Problem)이다. 직관적이면서 삶의 지혜를 담고 있는 문제이기도 하다. 문제 상황은 아래와 같다.

개발자 1명을 뽑는 채용 공고에 100명의 지원자가 몰렸다. 면접관은 1번부터 차례로 면접을 보고 면접이 끝나는 즉시 지원자에게 합격 여부를 알려줘야 한다. 불합격 처리된 지원자는 다시 부를 수 없고, 합격자가 나오면 면접이 끝나므로 나머지 지원자들의 면접은 취소된다. 이런 상황에서 어떻게 해야 가장 뛰어난 인재를 채용할 수 있을까?

만약 1-10번 지원자 중 바로 합격시킬 경우, 90% 확률로 나타날 더 좋은 지원자를 만나지도 못하고 놓치는 꼴이 된다. 그렇다고 1-70번 지원자를 모두 탈락시킬 경우, 남는 선택지는 고작 30명으로 줄어들게 되고 뛰어난 지원자를 이미 불합격시켰을 수 있다. 많은 사람들이 이 문제 상황에 답답함을 느끼는 이유는 100명을 모두 살펴보고 그중 제일 좋은 지원자를 뽑고 싶은 마음 때문이다. 내가 혹시나 너무 성급하게 결정하는 게 아닐까, 더 좋은 사람이 뒤에 나타나지 않을까라는 마음과 이미 탈락시킨 지원자를 아쉬워하는 마음 사이에서 갈팡질팡한다. 

이 문제에 대한 최적 해답은 다음과 같다. 우선 1번부터 37번까지는 면접을 보고 모두 불합격시킨다. 이후 남은 63명의 면접을 보면서 앞에 37명 중 제일 뛰어났던 사람보다 더 뛰어난 사람이 나타나면 즉시 채용하는 것이다. 

이 문제는 채용뿐만 아니라 배우자를 선택하는 문제, 사업 아이템을 고르는 문제, 회사를 고르는 문제 등 불확실한 상황에서 비가역적인 선택을 내려야 하는 대부분의 상황과 관련되어 있다. 물론 기계적으로 적용하는 건 어렵지만 하나의 기준점을 삼기에는 매우 유용하다. 나 역시 여러 번 도움을 받은 기억이 있다. 

우리는 모든 상황을 통제할 수 없다. 

첫 번째, 우리는 모든 상황을 통제할 수 없다는 사실이다. 선택의 순간에서 우리는 내가 내리는 선택이 최선인지 고민한다. 중요한 선택이라면 더더욱 깊게 고민을 할 수밖에 없다. 그러나 때로는 고민(개인의 노력)으로 넘을 수 없는 제약이 걸려 있는 경우도 있다. 100명 모두를 면접 보고 그중 제일 뛰어난 지원자를 뽑는다는 선택지는 나에게 없다는 의미이다. 어렵고 답답한 상황이지만 그래도 그 상황에 맞는 선택을 내려야 한다. 나의 고민이 제약조건 하에서 최적의 선택을 내리기 위한 노력인지, 제약조건을 받아들이지 못해 혼란스러운 마음에서 비롯된 고민인지 살펴볼 필요가 있다. 

매력적인 선택지라도 첫 타에 결정 내리는 건 조심해야 한다. 

때로는 처음 보는 매력적인 제안에 솔깃하는 경우가 있는데, 정말 처음 접하는 부류의 제안이라면 조심할 필요가 있다. 해당 제안이 좋은지 여부를 판단하기에 근거가 충분하지 않다. 지금은 좋아 보이지만 알고 나면 발에 치이는 그저 그런 제안 일 수 있다. 그렇다고 관심을 주지 말라는 의미는 아니다. 오히려 매우 면밀하게 살펴 이후 선택의 기준점으로 삼으려는 노력이 필요하다. 

생각보다 빠르게 선택을 내리는 게 좋을 수 있다.

100명 중 37명이라는 기준은 우리의 직관보다 매우 적은 숫자이다. 단적인 예로 20살부터 1년에 한 명 씩 총 10명과 연애를 하고 30살 전에 결혼을 생각한다고 가정해보자. 최적 전략에 따르면 앞에 3명과 헤어진 23살부터는 바로 결혼을 생각하면서 만나야 한다는 뜻이다. 최대 10명이나 만날 수 있으니 많이 만나보고 7-9번째에 결정하면 되겠지라고 착각하기 쉬우나 그렇지 않다. 게다가 37명은 지원자의 수준에 대한 사전 지식이 전혀 없다는 걸 가정한 것이다. 만약 대략적인 사전 분포를 안다고 가정하면, 37명보다 더 낮아진다. 즉, 한번 놓치면 돌이킬 수 없는 선택 상황에서는 우리 직관보다 훨씬 빠르게 결정을 내리는 게 좋다. 

비서 문제를 실제 상황에 적용하려면 몇 가지 가정이 필요하다. 나에게 주어진 선택지의 수를 가늠해야 하고, 시간에 따라 평가 기준이 바뀌지 않아야 하며, 동시에 매우 정확한 평가가 가능해야 한다. 또한 모든 조건이 완벽한 상황에서도 최고의 선택을 내릴 확률은 37%에 불과하다. 그럼에도 꽤나 많은 문제에 직관적인 기준점을 제공한다는 점에서 의미가 크다. 알고리즘의 세상에서 시간이 오래 걸리더라도 모든 경우의 수를 살펴 완벽한 답을 찾는 방식이 있는 반면, 매우 짧은 계산으로 그럴싸한 답을 찾는 방식도 있다. 우리 삶도 비슷하다. 완벽한 선택을 내리기 위한 깊은 고민이 능사가 아니란 뜻이다. 때로는 적당히 고민하고 빠르게 내린 결정이 더 나은 결과를 가져다 주기도 한다.