언제 멈춰야 하나

카드 10장을 차례로 뒤집으며 가장 큰 숫자를 맞히는 게임을 해 봅니다. 너무 일찍 고르면 뒤에 더 큰 카드가 나와서 후회하고, 너무 늦게 고르면 이미 좋은 카드가 지나가 버립니다.

앞의 몇 장은 기준을 세우기 위해 그냥 흘려보내고, 그 뒤부터 지금까지 본 것 중 가장 큰 숫자가 나오면 바로 낚아채는 전략이 제일 잘 통합니다.

전체 명의 지원자 중 앞의 명은 무조건 탈락시키며 최고 점수를 파악합니다. 그리고 번째부터 그 최고 점수를 경신하는 첫 번째 사람을 즉시 채용합니다.

최고 지원자가 번째()에 있을 때 합격하려면, 1등 바로 전까지의 구간에서 가장 뛰어난 사람이 앞의 탐색 구간 명 안에 들어 있어야 합니다. 그 확률들을 모두 더해 최적의 를 찾습니다.

성공 확률 함수는 로 주어집니다. 로 두고 연속 극한을 취하면 가 됩니다.

이 함수를 미분하여 극댓값을 구하면 에서 가 도출됩니다. 따라서 전체의 약 36.8%를 탐색한 후 기준을 적용할 때 성공 확률 역시 로 극대화됩니다.

비서 문제는 확률론의 최적 정지 이론(Optimal Stopping Theory)과 동적 계획법의 대표적 고전입니다. 불완전한 정보와 되돌릴 수 없는 시간의 화살 속에서 탐색(Exploration)과 활용(Exploitation) 사이의 수학적 균형점을 제시합니다.

부동산 매매, 알고리즘 트레이딩의 주문 집행 시점 결정, 온라인 데이팅 앱의 매칭 알고리즘 등 한정된 자원으로 결정을 내려야 하는 현실의 복잡한 최적화 모델에 응용됩니다.