최적 정지 문제와 37% 법칙: 앞선 1/e를 살핀 뒤 최고의 선택을 찾는 계산

후보를 한 명씩 만나야 하고, 지나간 후보에게는 다시 연락할 수 없다고 가정해 보겠습니다. 너무 일찍 결정하면 뒤에 더 좋은 후보가 있을 수 있고, 너무 오래 기다리면 이미 만난 최고의 후보를 놓칠 수 있습니다. 이처럼 관찰을 계속할지 지금 멈추고 선택할지를 정하는 수학 문제가 최적 정지 문제입니다. 그중 가장 널리 알려진 고전 비서 문제에는 ‘37% 법칙’이라는 정확한 해법이 있습니다.

37% 법칙은 전체 후보의 앞부분 약 1/e, 즉 약 36.8%를 선택하지 않고 관찰한 뒤, 이후에 관찰 구간의 모든 후보보다 뛰어난 첫 후보를 즉시 선택하는 전략입니다. 후보가 충분히 많을 때 이 전략이 전체 1등을 고를 확률을 가장 크게 만들며, 그 최대 성공 확률 역시 약 1/e입니다. 다만 이 결론은 정해진 가정 아래에서만 성립합니다. 모든 채용, 집 구하기, 연애 같은 현실 문제에 그대로 적용되는 보편 법칙은 아닙니다.

최적 정지 문제란 무엇인가요?

최적 정지는 순서대로 들어오는 정보를 살펴보다가 언제 관찰을 끝내고 행동할지를 정하는 문제입니다. 미래의 관측값은 아직 알 수 없고, 현재까지 확보한 정보만으로 멈춤 여부를 결정해야 합니다. 목표는 문제에 따라 당첨 확률, 기대 보상 또는 비용 등을 가장 유리하게 만드는 것입니다.

37% 법칙이 답이 되는 것은 최적 정지 문제 전체가 아니라 ‘최고의 선택 문제’ 또는 ‘비서 문제’라고 불리는 특정 모형입니다. 미국 통계학자 존 길버트와 프레더릭 모스텔러는 1966년 논문에서 이 문제와 여러 변형을 체계적으로 분석했습니다. 이 문제의 기원은 더 복잡하며, 토머스 퍼거슨은 1989년 논문에서 여러 초기 연구와 전파 과정을 정리했습니다.

37% 법칙이 성립하는 일곱 가지 조건

계산을 시작하려면 고전 비서 문제가 어떤 상황을 가정하는지부터 확인해야 합니다. 조건이 바뀌면 최적 전략과 기준점도 달라지기 때문입니다.

1. 전체 후보 수 n을 미리 알고 있습니다.
2. 후보들은 공동 1등 없이 서로 다른 순위를 가집니다.
3. 후보가 나타나는 순서는 가능한 모든 순열 가운데 무작위입니다.
4. 후보를 한 명씩 차례대로 평가합니다.
5. 현재 후보가 지금까지 본 후보들 가운데 몇 등인지는 알 수 있지만, 전체 분포나 절대 점수는 모릅니다.
6. 각 후보를 본 직후 선택하거나 거절해야 하며, 거절한 후보에게 돌아갈 수 없습니다.
7. 단 한 명만 선택하고, 목표는 전체 후보 가운데 절대 1등을 고를 확률을 최대화하는 것입니다.

여기에서 ‘무작위 순서’는 핵심 조건입니다. 좋은 후보가 의도적으로 앞이나 뒤에 몰리거나 도착 순서가 후보의 수준과 관련되어 있다면 아래 계산은 그대로 적용되지 않습니다. 후보 수를 모르거나, 거절한 후보를 다시 부를 수 있거나, 1등이 아니라 상위권이면 충분한 경우에도 다른 모형이 필요합니다.

37% 법칙을 실제 절차로 바꾸면

전체가 n명일 때 먼저 m명을 관찰 구간으로 정합니다. 이 m명은 누가 아무리 좋아 보여도 선택하지 않습니다. 대신 관찰 구간에서 가장 뛰어난 후보의 수준을 기준으로 저장합니다. 그런 다음 m+1번째 후보부터 살펴보다가 앞서 본 모든 후보보다 좋은 사람이 처음 나타나면 바로 선택합니다.

관찰 단계: 앞선 약 36.8%를 모두 보류 → 선택 단계: 지금까지의 최고 기록을 처음 경신한 후보를 채택

‘37% 이후 첫 후보를 고른다’는 뜻은 아닙니다. 37% 이후에 나타난 후보가 관찰 구간의 최고 후보보다도 좋아야 합니다. 확률론에서는 앞서 나온 모든 관측값보다 큰 값을 ‘기록’이라고 부르므로, 이 전략은 관찰 구간 뒤에 처음 나오는 새 기록을 고르는 방식입니다.

끝까지 새 기록이 나오지 않으면 전체 1등이 관찰 구간 안에 있었다는 뜻입니다. 일부 설명에서는 마지막 후보를 선택하는 것으로 절차를 마무리하지만, 이때는 이미 전체 1등을 고를 수 없으므로 그 규칙은 성공 확률 계산에 영향을 주지 않습니다.

왜 처음부터 마음에 드는 후보를 고르면 안 될까요?

첫 후보를 바로 선택하면 그 사람이 전체 1등일 확률은 정확히 1/n입니다. 후보가 100명이면 성공 확률은 1%뿐입니다. 반대로 거의 끝까지 기다리면 앞부분에 있던 1등을 되돌아가 선택할 수 없고, 마지막 몇 명 안에 1등이 있을 가능성도 작습니다.

관찰 구간은 후보들의 상대적인 수준을 파악하게 해 줍니다. 그러나 관찰 구간을 길게 잡을수록 기준은 정교해지는 대신, 그 구간 안에 전체 1등이 들어와 버릴 가능성이 커집니다. 37% 법칙은 기준을 만드는 데 쓰는 정보와 선택 기회를 남겨 두는 비율 사이의 균형을 계산한 결과입니다.

성공 확률 공식은 어떻게 만들어질까요?

전체 n명 중 처음 m명을 보류한다고 하겠습니다. 전체 1등이 t번째 자리에 올 확률은 어느 자리에서나 1/n입니다. 전략이 성공하려면 t는 반드시 m보다 커야 하고, t가 오기 전에 선택 단계에서 다른 후보를 잘못 골라서도 안 됩니다.

전체 1등이 t번째에 있다고 조건을 붙여 보겠습니다. t번째 앞에는 t-1명이 있습니다. 이들 가운데 가장 좋은 후보가 처음 m명의 관찰 구간 안에 있으면, m+1번째부터 t-1번째까지는 관찰 구간의 기록을 깨는 사람이 없습니다. 따라서 전략은 기다렸다가 t번째의 전체 1등을 선택합니다. t-1명 가운데 최고가 앞선 m명 안에 있을 확률은 m/(t-1)입니다.

Pₙ(m) = (m/n) × [1/m + 1/(m+1) + ··· + 1/(n-1)]

각 가능한 위치 t=m+1부터 n까지 성공 확률을 더하면 위 공식이 나옵니다. 같은 식을 합 기호로 쓰면 Pₙ(m)=(m/n)Σ(j=m부터 n-1까지)1/j입니다. 대괄호 안은 조화수의 차이 Hₙ₋₁-Hₘ₋₁와 같습니다. 이 공식은 후보 수가 유한할 때 각 m의 성공 확률을 정확히 비교하는 데 사용할 수 있습니다.

다섯 명 사례로 공식을 직접 확인하기

후보가 5명이고 처음 2명을 보류한 뒤 3번째부터 새 기록을 선택한다고 하겠습니다. 전체 1등이 3번째에 오면 성공 확률에 1/5이 더해집니다. 4번째에 오면 앞선 3명 중 최고가 관찰 구간 2명 안에 있어야 하므로 (1/5)×(2/3)입니다. 5번째에 오면 같은 조건의 확률은 (1/5)×(2/4)입니다.

1/5 + (1/5×2/3) + (1/5×2/4) = 13/30 ≈ 43.33%

후보 5명에서는 처음 2명을 보류하는 전략이 최적이며 성공 확률은 약 43.33%입니다. 후보 수가 작은 경우에는 단순히 36.8%를 기계적으로 반올림하기보다 가능한 정수 기준을 정확한 공식으로 비교해야 합니다.

1/e와 36.8%는 어디에서 나올까요?

후보 수가 매우 크면 m/n을 x라는 비율로 놓을 수 있습니다. 조화합 1/m+1/(m+1)+···+1/(n-1)은 로그 함수 ln(n/m)에 가까워집니다. n/m은 약 1/x이므로 성공 확률은 다음과 같이 근사됩니다.

P(x) ≈ x ln(1/x) = -x ln x

이 함수를 미분하면 P′(x)=-ln x-1입니다. 기울기가 0이 되는 지점은 ln x=-1, 즉 x=e⁻¹=1/e입니다. 두 번째 미분 P″(x)=-1/x는 0과 1 사이에서 음수이므로 이 지점은 최댓값입니다. 자연로그의 밑인 e는 약 2.71828이고, 1/e는 약 0.367879입니다.

최적 관찰 비율 x=1/e≈36.7879%, 최대 성공 확률 P(1/e)=1/e≈36.7879%

1/e가 두 번 등장한다는 점을 구분해야 합니다. 하나는 선택하지 않고 관찰하는 최적 비율이고, 다른 하나는 그 전략으로 전체 1등을 선택할 수 있는 극한 확률입니다. 두 값은 이 모형에서 우연히 같은 것이 아니라 P(x)=-x ln x에 x=1/e를 대입했기 때문에 같습니다.

후보가 100명이면 정확히 몇 명을 지나쳐야 할까요?

1/e에 100을 곱하면 약 36.79이지만 사람 수는 정수여야 합니다. 정확한 유한 공식으로 모든 기준을 비교하면 처음 37명을 보류하고 38번째부터 판단하는 전략이 최적입니다. 이때 전체 1등을 고를 확률은 약 0.37104278, 즉 37.10%입니다. 극한값 36.79%보다 조금 높습니다.

표에서 후보 수가 커질수록 최적 관찰 비율과 성공 확률이 1/e에 가까워지는 모습을 볼 수 있습니다. ‘앞선 37%’는 기억하기 쉬운 근삿값이고, 작은 n에서는 최적 정수가 비율의 단순 반올림과 다를 수 있습니다.

관찰 비율을 바꾸면 성공 확률은 어떻게 달라질까요?

후보가 100명일 때 정확한 공식을 적용하면 처음부터 선택하는 전략의 성공 확률은 1%입니다. 10명을 보류하면 약 23.48%, 25명을 보류하면 약 35.04%로 올라갑니다. 37명을 보류할 때 약 37.10%로 최대가 되고, 50명을 보류하면 약 34.91%로 다시 내려갑니다.

37% 주변에서는 곡선이 완만하지만 너무 이르거나 너무 늦게 선택을 시작하면 성공 확률이 크게 낮아집니다. 절반을 관찰하는 전략도 상당히 높은 성공률을 보이지만, 고전 모형에서 계산되는 최적점은 절반이 아니라 1/e입니다.

성공 확률이 왜 63.2%가 아니라 36.8%인가요?

처음 36.8%를 지나쳤으니 나머지 63.2%에서 1등을 찾을 확률이 63.2%라고 생각하기 쉽습니다. 그러나 1등이 뒤쪽에 있다는 사실만으로는 충분하지 않습니다. 선택 구간 초반에 관찰 기준을 깨는 후보가 나타나면 전략은 그 후보를 선택하고 멈춥니다. 뒤에 진짜 1등이 남아 있어도 볼 수 없습니다.

실패는 크게 두 경로로 생깁니다. 전체 1등이 애초에 관찰 구간에 들어오면 반드시 놓칩니다. 전체 1등이 선택 구간에 있더라도, 그 전에 나타난 새 기록을 먼저 선택하면 실패합니다. 두 조건을 모두 피한 경우만 성공이므로 최적 성공 확률은 약 36.8%입니다.

37% 법칙에서 자주 생기는 오해

앞선 37% 중 가장 좋은 후보를 나중에 선택하나요?

아닙니다. 고전 문제에서는 거절한 후보에게 돌아갈 수 없습니다. 앞선 후보들은 선택 대상이 아니라 비교 기준을 만드는 표본입니다. 되돌아갈 수 있다면 문제의 구조와 최적 전략이 달라집니다.

37번째 후보를 반드시 선택하나요?

아닙니다. 100명이라면 처음 37명을 보류하고 38번째부터 선택 가능성이 생깁니다. 38번째 후보가 앞선 37명 모두보다 좋아야 선택합니다. 그렇지 않으면 이후에 새 기록이 나올 때까지 계속 봅니다.

후보가 10명이면 정확히 3.68명을 관찰하나요?

사람 수는 정수이므로 그럴 수 없습니다. 정확한 계산에서는 10명 중 처음 3명을 보류하고 4번째부터 선택하는 전략이 최적이며, 성공 확률은 약 39.87%입니다. 1/e는 후보 수가 커질 때의 극한 비율입니다.

후보의 절대 점수를 알면 같은 법칙을 쓰나요?

반드시 그렇지는 않습니다. 고전 모형은 지금까지 본 후보 사이의 상대 순위만 이용합니다. 후보 점수의 확률분포를 알고 절대 점수를 관측할 수 있다면, 남은 기회와 점수에 따라 달라지는 다른 임계값 전략이 더 적합할 수 있습니다.

현실의 채용·집 구하기에 그대로 적용하기 어려운 이유

비서 문제는 순차적 선택의 핵심을 선명하게 보여 주지만 현실 조건은 대개 더 복잡합니다. 채용 후보에게 공동 순위가 있을 수 있고, 면접 순서는 무작위가 아닐 수 있으며, 좋은 후보가 회사의 제안을 거절할 수도 있습니다. 기업은 한 명의 절대 1등보다 기준을 충족하는 여러 사람 중 한 명을 찾는 경우도 많습니다.

집을 구할 때도 매물 수를 미리 확정하기 어렵고, 새 매물이 계속 추가되며, 가격·위치·면적처럼 여러 기준을 함께 판단합니다. 이미 본 매물이 아직 거래되지 않았다면 되돌아갈 수도 있습니다. 이런 조건들은 ‘n을 알고, 순서가 무작위이며, 되돌아갈 수 없고, 오직 전체 1등만 성공’이라는 고전 가정과 다릅니다.

따라서 현실에서 앞선 36.8%를 무조건 버려야 한다는 결론은 나오지 않습니다. 37% 법칙을 적용하려면 먼저 실제 상황이 고전 비서 문제의 조건을 얼마나 충족하는지 확인해야 합니다. 조건을 충족하지 않으면 후보 수가 미지수인 모형, 되돌림이 가능한 모형, 여러 명을 선택하는 모형 또는 기대 효용을 최대화하는 모형으로 계산을 바꿔야 합니다.

목표가 달라지면 최적 기준도 달라집니다

고전 비서 문제의 목적함수는 전체 1등을 맞히면 1, 아니면 0입니다. 2등을 골라도 실패로 처리합니다. 그러나 평균 순위를 가장 높이고 싶거나, 일정 기준 이상의 후보면 충분하거나, 상위 k명 중 한 명을 고르면 성공이라고 정의하면 같은 성공 확률 공식이 적용되지 않습니다.

• 상위 몇 퍼센트 안에 드는 후보면 성공인 경우
• 후보의 순위가 아니라 실제 가치의 기대값을 최대화하는 경우
• 한 명이 아니라 여러 명을 선택할 수 있는 경우
• 후보 수 n을 사전에 알 수 없는 경우
• 관찰이나 거절에 비용이 발생하는 경우
• 거절한 후보에게 다시 제안할 수 있는 경우
• 후보 순서가 무작위가 아니거나 동점이 있는 경우

이런 변형에서는 1/e가 최적이라는 보장이 없습니다. 최적 정지 문제는 ‘언제 멈출 것인가’라는 공통 질문을 다루지만, 답은 정보 구조와 보상 규칙에 따라 달라집니다.

최적 정지 문제와 37% 법칙 핵심 정리

고전 비서 문제에서는 전체 후보 수를 알고, 후보가 무작위 순서로 오며, 한 번 거절하면 되돌아갈 수 없습니다. 목표는 오직 전체 1등을 선택하는 것입니다. 이 조건에서 처음 m명을 관찰하고 이후 첫 새 기록을 선택하는 전략의 성공 확률은 (m/n)Σ1/j로 계산됩니다.

후보 수가 커질 때 관찰 비율을 x=m/n으로 두면 성공 확률은 -x ln x에 가까워집니다. 이 함수는 x=1/e에서 최대가 되므로 앞선 약 36.8%를 관찰하고 이후 처음으로 기존 최고를 넘어선 후보를 선택합니다. 최대 성공 확률도 약 36.8%로 수렴합니다.

후보가 100명일 때는 정확히 37명을 보류하고 38번째부터 판단하는 것이 최적이며 성공 확률은 약 37.10%입니다. 이 결과는 불확실한 순차 선택에서 정보 수집과 선택 기회 사이의 균형을 수학적으로 보여 줍니다. 동시에 조건이 달라지면 37%라는 숫자도 달라진다는 점까지 함께 기억해야 정확한 법칙입니다.

참고 자료

• Statistics LibreTexts, The Secretary Problem/12%3A_Finite_Sampling_Models/12.09%3A_The_Secretary_Problem)
• Carnegie Mellon University, Probability and Computing 강의 노트
• Gilbert and Mosteller, Recognizing the Maximum of a Sequence, Journal of the American Statistical Association
• Thomas S. Ferguson, Who Solved the Secretary Problem?, Statistical Science
• University of Bielefeld, The 37 Percent Rule