비서 문제 (최적 정지)
37% 법칙: 최적의 선택을 위해 얼마나 관찰해야 할까? 비서 문제의 최적 정지 전략.
비서 문제(최적 정지 문제)는 n명의 후보를 순서대로 면접할 때 최고의 후보를 선택하는 최적 전략을 분석합니다. 핵심은 37% 법칙으로, 처음 ⌊n/e⌋명은 관찰만 하고 이후 이전 최고보다 나은 첫 후보를 선택하면 최적입니다. 100명 중 최고를 뽑으려면 처음 36명은 관찰만 하고 37번째부터 기준 이상인 후보를 선택합니다. 이 전략으로 최고를 뽑을 확률은 약 36.8%(1/e)이며, 이것이 가능한 최대 확률입니다. 채용, 주택 구매, 결혼 등 되돌릴 수 없는 순차 선택 상황에서 최적 의사결정 전략을 이해하세요. 다양한 관찰 비율에 따른 성공 확률 변화도 차트로 비교할 수 있습니다.
사용 방법
총 소요 시간: 약 30초
후보 수 입력
전체 후보(또는 선택지) 수를 입력합니다.
시뮬레이션 설정
시뮬레이션 횟수를 설정합니다.
결과 확인
최적 관찰 수, 성공 확률, 관찰 수별 성공률 차트를 확인합니다.
계산 원리
비서 문제에서 n명의 후보 중 처음 k명을 관찰하고, k+1번째부터 이전 최고보다 나은 첫 후보를 선택하는 전략의 성공 확률은: P(k) = (k/n) × Σ(i=k→n-1) 1/i. 이 확률을 k에 대해 최대화하면, n이 클 때 최적 k/n → 1/e ≈ 0.3679이고, 최대 성공 확률도 1/e ≈ 36.8%에 수렴합니다.
증명의 핵심은 최적 후보가 j번째(j > k)에 있을 때, 이 후보가 선택될 조건이 "k+1번째부터 j-1번째까지 이전 최고를 갱신하는 후보가 없는 것"이라는 점입니다. 이 확률은 k/(j-1)이므로, 전체 성공 확률은 (1/n) × Σ(j=k+1→n) k/(j-1) = (k/n) × Σ(i=k→n-1) 1/i.
e = 2.71828...은 자연상수로, 이 문제에서는 "관찰과 선택의 균형점"을 나타냅니다. 관찰을 많이 하면 기준은 좋아지지만 이미 최고를 놓칠 확률이 올라가고, 적게 하면 기준이 낮아 나쁜 후보를 선택할 위험이 있습니다. 1/e가 이 두 효과의 최적 균형점입니다.
자주 묻는 질문
실생활 예시
10명 면접 최적 전략
10명의 면접자가 있을 때, 최적 정지 전략은 처음 3~4명을 관찰만 하고 이후 이전 최고보다 나은 첫 번째 후보를 채용합니다. 이 전략의 성공 확률은 약 39.9%입니다.
단 10명이라도 최적 전략을 쓰면 무작위(10%)보다 4배 높은 확률로 최고의 후보를 선택할 수 있습니다.
주택 구매 전략
20채의 매물을 순서대로 보고 즉시 결정해야 한다면, 처음 7채는 시세 파악만 하고 8번째부터 이전 최고보다 나은 첫 매물을 구매합니다. 최적 매물을 선택할 확률은 약 38.4%입니다.
실전에서는 매물이 무한하지 않고 돌아갈 수도 있지만, 37% 법칙은 "얼마나 탐색한 후 결정할지"에 대한 좋은 기준을 제공합니다.
연애와 결혼 시기 결정
20세부터 35세까지 15년간 만남의 기회가 있다면, 37% 법칙에 따라 처음 5.5년(약 25.5세까지)은 만남의 경험을 쌓고, 이후 그때까지의 최고보다 나은 상대를 만나면 결정합니다.
물론 사람 관계를 수학 공식에 맞추는 것은 현실적이지 않지만, "충분히 경험한 후 결정하라"는 원칙은 유용한 지혜입니다. 너무 일찍 결정하거나 너무 늦게까지 망설이는 것 모두 비효율적입니다.
중고차 구매 전략
온라인에서 15대의 중고차 매물을 순서대로 확인합니다. 37% 법칙에 따라 처음 5~6대는 가격과 상태를 비교만 하고, 7번째부터 이전에 본 것보다 좋은 첫 매물을 구매합니다.
이 전략으로 가장 좋은 매물을 선택할 확률은 약 37.5%로, 매물을 하나씩 순서대로 판단해야 하는 상황에서 최적의 접근입니다.
이직 시 최적 입사 시기
6개 회사에서 순차적으로 최종 면접 결과를 받습니다. 37% 법칙에 따라 처음 2곳의 제안은 기준 수립용으로 보고, 3번째부터 이전 제안보다 나은 첫 회사에 입사합니다. 최적 선택 확률은 약 42.7%입니다.
후보 수가 적을수록 성공 확률이 높아집니다. 6개면 무작위(16.7%)보다 2.5배 높은 확률로 최고의 제안을 선택할 수 있습니다.
용어 사전
- 최적 정지 문제
- 순차적으로 정보가 주어질 때, 최적의 시점에 탐색을 멈추고 결정을 내리는 문제. 비서 문제가 가장 유명한 예시입니다.
- 37% 법칙(1/e 법칙)
- 전체 선택지의 약 37%(1/e)를 관찰한 후, 그때까지의 최고보다 나은 첫 번째를 선택하는 전략. 수학적으로 증명된 최적 전략입니다.
- 자연상수(e)
- e ≈ 2.71828로, 자연로그의 밑. 비서 문제에서 최적 관찰 비율 1/e ≈ 0.3679를 결정합니다.
- 순차 선택
- 선택지를 한 번에 하나씩 순서대로 평가하고, 각각에 대해 즉시 수락/거절을 결정해야 하는 상황. 거절한 선택지로 돌아갈 수 없습니다.
- 관찰 기간
- 선택하지 않고 정보만 수집하는 초기 구간. 37% 법칙에서 처음 n/e명을 면접하되 채용하지 않는 기간입니다.
- 기준 갱신
- 관찰 기간 동안 만난 후보 중 최고를 기준으로 설정하고, 이후 이 기준을 초과하는 첫 후보를 선택하는 방식.
- 정보의 가치
- 추가 탐색으로 얻는 정보가 더 나은 결정을 가능하게 하는 정도. 비서 문제에서 관찰 기간은 정보 수집의 비용과 가치 사이의 균형입니다.