개요

비서 문제는 수학의 '최적 멈춤' 문제 중 하나이다.

  • 비서 1명을 뽑는 입사 공고를 냈더니 n 명의 입사 지원자가 몰려들었다.
  • 인사 담당자는 1명씩 면접을 보고 면접이 끝나는 즉시 지원자에게 합격 여부를 알려줘야 한다.
  • 불합격 처리된 지원자는 다시 부를 수 없다.
  • 합격자가 나오면 면접이 끝나므로, 나머지 지원자들의 면접은 취소된다.
  • 어떻게 해야 가장 뛰어난 인재를 채용할 수 있을까?

이 문제의 주인공이 처한 난감한 점은 다음과 같다.

  • n 명의 지원자들 중 누가 가장 뛰어난지 알기 위해서는 n 번의 면접을 보아야 한다.
    • 즉 지원자가 너무 많을 경우, 몇 명까지 면접을 보고 채용을 종료할지 고민해야 한다.
  • 면접을 적게 보고 채용을 하면, 면접을 안 본 사람들 중에 더 뛰어난 지원자가 있을 수 있다.
  • 불합격을 많이 주고 채용을 하면, 가장 뛰어난 지원자를 이미 불합격시켰을 수 있다.

가장 뛰어난 지원자를 합격시킬 확률을 최대로 하려면 인사담당자는 어떻게 해야 할까?

이 문제는 이미 해결된 것으로, 해답은 약 37%의 지원자들을 먼저 면접을 본 다음, 이후 먼저 면접을 본 사람들보다 뛰어난 지원자가 나타나면 즉시 채용을 하는 것이다.

다음의 방법을 수행하면 된다.

  1. \(n \times 0.37\) 명까지 면접을 보고 불합격시킨다.
  2. 불합격된 지원자들 중 가장 뛰어났던 지원자의 점수를 컷트라인 점수로 정한다.
  3. 다음 지원자 면접을 본다.
    • 면접을 본 결과 컷트라인 점수보다 높은 점수가 나오면 합격시키고 채용을 종료한다.
    • 그렇지 않다면 3을 반복한다.

이 문제는 채용 외에도 주택 선택, 주차장 찾기, 회사 그만둘 시점 선택 등의 다양한 문제에 응용이 가능하다.

왜 37% 일까?

지원자가 100 명이 있다고 생각해 보자.

  • 1번째 지원자 : 지금까지 본 사람 중 최고! (1명만 면접을 봤으므로)
  • 2번째 지원자 : 지금까지 본 사람 중 최고일 확률은 \(\frac{1}{2}\)
  • 3번째 지원자 : 지금까지 본 사람 중 최고일 확률은 \(\frac{1}{3}\)
  • …
  • 100번째 지원자 : 지금까지 본 사람 중 최고일 확률은 \(\frac{1}{100}\)

즉 면접을 너무 많이 보는 것은 현명한 선택이 아니다.

게다가 자원 또한 한정되어 있어 언제까지나 면접만 보고 있을 수는 없다.

따라서 일정 인원을 살펴보고 커트라인 점수를 정한 다음, 이후 커트라인 점수를 초과한 최초의 지원자를 합격시키는 전략을 생각할 수 있다.

살펴보기 전략

살펴보기 전략을 실행할 대상이 되는 입사 지원자가 n 명이라고 생각해 보자.

지원자가 1 ~ 2명인 경우

  • 지원자가 1명 : 그냥 채용하면 된다. 끝.
  • 지원자가 2명 : 두 사람 중 더 나은 사람을 채용할 확률은 \(\frac{1}{2}\).
    • 확률이 반반이라면 면접을 볼 것도 없이 1등으로 지원한 사람을 채용하는 쪽이 효율적이다.

지원자가 3 명인 경우

그러나 지원자가 3명인 경우부터는 다음과 같이 3 가지 전략이 가능할 것이다.

  • 0명 살펴보기 전략: 첫번째 지원자를 합격시킨다.
  • 1명 살펴보기 전략: 첫 1명을 불합격시킨 다음, 두번째 지원자가 앞의 지원자보다 뛰어난지를 본다.
  • 2명 살펴보기 전략: 세번째 지원자를 합격시킨다.

0명 살펴보기 전략과 2명 살펴보기 전략은 최고의 지원자를 합격시킬 확률이 \(\frac{1}{3}\) 이다.

그렇다면 1명 살펴보기 전략이 최고의 지원자를 합격시킬 확률은 어떻게 될까?

참고로 3 - 2 - 1 순으로 뛰어난 역량을 갖고 있다. 숫자가 랭크라고 생각하자.

경우 1번 면접 2번 면접 3번 면접 전략 성공?
1 1 지원자 2 지원자 3 지원자 실패. 1 지원자 불합격 후, 2지원자 채용.
2 1 지원자 3 지원자 2 지원자 성공. 1 지원자 불합격 후, 3지원자 채용.
3 2 지원자 1 지원자 3 지원자 성공. 2, 1 지원자 불합격 후, 3 지원자 채용.
4 2 지원자 3 지원자 1 지원자 성공. 2 지원자 불합격 후, 3 지원자 채용.
5 3 지원자 1 지원자 2 지원자 실패. 3, 1 지원자 불합격 후, 2 지원자 채용.
6 3 지원자 2 지원자 1 지원자 실패. 3, 2 지원자 불합격 후, 1 지원자 채용.

모든 경우의 수를 살펴봤을 때 실패가 3 건이고, 성공이 3 건이므로 이 전략의 성공 확률은 50% 나 된다.

즉 지원자가 3명인 경우 "1명 살펴보기"가 최적의 전략이 된다.

  • 0명 살펴보기 전략: 성공 확률 \(\frac{1}{3} = 33.33\%\)
  • 1명 살펴보기 전략: 성공 확률 \(\frac{1}{2} = 50\%\)
  • 2명 살펴보기 전략: 성공 확률 \(\frac{1}{3} = 33.33\%\)

지원자가 4 ~ 9명인 경우

그렇다면 지원자가 4명일 경우는 어떻게 될까?

다음과 같은 전략을 생각해 볼 수 있을 것이다.

  • 0명 살펴보기 전략 - 성공 확률 \(\frac{1}{4}\)
  • 1명 살펴보기 전략 - ?
  • 2명 살펴보기 전략 - ?
  • 3명 살펴보기 전략 - 성공 확률 \(\frac{1}{4}\)

이 문제는 코딩으로 풀어보면 재미있을 것 같아서 다음과 같이 9명 경우까지 계산할 수 있는 코드를 작성해 보았다.

// 주어진 문자열로 가능한 모든 순열 목록을 만든다
function permutator(candidates) {
    const input = candidates.split('');
    let set = [];
    function mix(arr, m) {
        if (arr.length === 0) {
            return set.push(m);
        }
        for (let i = 0; i < arr.length; i++) {
            const curr = arr.slice();
            const next = parseInt(curr.splice(i, 1), 10);
            mix(curr.slice(), m.concat(next))
        }
    }
    mix(input, [])
    return set;
}

// 1234... 형식의 문자열을 만든다
function createNumStr(num) {
    let str = '';
    for (let i = 1; i <= num; i++) {
        str = str.concat(i);
    }
    return str;
}

// 순서대로 면접보며 passLimit 보다 높은 첫번째 지원자를 채용한다
function hire(passLimit, remain) {
    for (let i = 0; i < remain.length; i++) {
        if (remain[i] >= passLimit) {
            return remain[i];
        }
    }
    return remain[remain.length - 1];
}

const result = [];

for (let i = 4; i < 10; i++) {

    // 최고의 결과를 낸 전략을 기록한다
    let best = { 'candidates': i, 'preview': 0, 'probability': 0 };

    console.log(`지원자: ${i}명`)

    for (let j = 1; j < i - 1; j++) {

        // 모든 경우
        const cases = permutator(createNumStr(i));

        // 성공: 가장 우수한 지원자를 채용
        const success = cases
            .map((candidates) => {
                const preview = candidates.slice(0, j);
                const passLimit = Math.max(...preview);
                const remain = candidates.slice(j);

                return hire(passLimit, remain);
            })
            .filter((passed) => passed == i );

        // 이 전략의 성공 확률
        const probability = success.length / cases.length;

        if (best.probability > probability) {
            break;
        }
        if (best.probability < probability) {
            best.preview = j;
            best.probability = probability;
        }
        console.log(`\t전략: ${j}명 살펴보기. 채용 성공 확률: ${success.length} / ${cases.length}`);
    }
    result.push(best);
}
console.log(result);

위의 코드를 실행해보면 다음과 같은 결과가 출력된다.

지원자: 4명
	전략: 1명 살펴보기. 채용 성공 확률: 11 / 24
지원자: 5명
	전략: 1명 살펴보기. 채용 성공 확률: 50 / 120
	전략: 2명 살펴보기. 채용 성공 확률: 52 / 120
지원자: 6명
	전략: 1명 살펴보기. 채용 성공 확률: 274 / 720
	전략: 2명 살펴보기. 채용 성공 확률: 308 / 720
지원자: 7명
	전략: 1명 살펴보기. 채용 성공 확률: 1764 / 5040
	전략: 2명 살펴보기. 채용 성공 확률: 2088 / 5040
지원자: 8명
	전략: 1명 살펴보기. 채용 성공 확률: 13068 / 40320
	전략: 2명 살펴보기. 채용 성공 확률: 16056 / 40320
	전략: 3명 살펴보기. 채용 성공 확률: 16524 / 40320
지원자: 9명
	전략: 1명 살펴보기. 채용 성공 확률: 109584 / 362880
	전략: 2명 살펴보기. 채용 성공 확률: 138528 / 362880
	전략: 3명 살펴보기. 채용 성공 확률: 147312 / 362880
[ { candidates: 4, preview: 1, probability: 0.4583333333333333 },
  { candidates: 5, preview: 2, probability: 0.43333333333333335 },
  { candidates: 6, preview: 2, probability: 0.42777777777777776 },
  { candidates: 7, preview: 2, probability: 0.4142857142857143 },
  { candidates: 8, preview: 3, probability: 0.40982142857142856 },
  { candidates: 9, preview: 3, probability: 0.40595238095238095 } ]

결과를 정리하자면 다음과 같다.

지원자 최적의 살펴보기 수 성공 확률 살펴보기 / 지원자
4 1 45.83% \(\frac{1}{4} = 0.25\)
5 2 43.33% \(\frac{2}{5} = 0.4\)
6 2 42.77% \(\frac{2}{6} = 0.33..\)
7 2 41.42% \(\frac{2}{7} = 0.2857..\)
8 3 40.98% \(\frac{3}{8} = 0.375\)
9 3 40.59% \(\frac{3}{9} = 0.33..\)
  • 여기에서 주목해야 할 숫자는 살펴보기 / 지원자라 할 수 있다.
  • 이 값이 바로 n 명이 있을 때 어느 정도의 비율을 살펴보기해야 하는지를 알려주는 값이기 때문이다.

좀 더 큰 n 값에 대한 결과는 다음과 같다. 자료의 출처는 [[Algorithms-to-Live-By]]{알고리즘, 인생을 계산하다} 32쪽이다.

지원자 최적의 살펴보기 수 성공 확률 살펴보기 / 지원자
10 3 39.87% \(\frac{3}{10} = 0.3\)
20 7 38.42% \(\frac{7}{20} = 0.35\)
30 11 37.86% \(\frac{11}{30} = 0.366..\)
40 15 37.57% \(\frac{15}{40} = 0.375\)
50 18 37.43% \(\frac{18}{50} = 0.36\)
100 37 37.10% \(\frac{37}{100} = 0.37\)
1000 369 36.81% \(\frac{369}{1000} = 0.369\)

숫자가 1000 에 가까워질수록 0.369로 가까워진다는 것을 알 수 있다.

즉, 지원자가 1000명이라면 369명을 살펴보고 이후에 합격자를 뽑으면 된다.

사실은 37%가 아니라 \(\frac{1}{e} = 36.78..\%\)

앞에서 4 ~ 9명인 경우를 계산한 코드는 순열을 이용하기 때문에 \(O(n!)\)로 돌아간다.

가령, 지원자 수에 따라 적어도 다음과 같은 만큼의 루프를 돌게 된다.

  • 지원자가 10명일 때 모든 경우의 수: \(10! = 3628800\)
  • 지원자가 20명일 때 모든 경우의 수 \(20! = 2432902008176640000\)

따라서 더 나은 알고리즘을 찾아 적용하거나, 수학으로 풀어내는 방법이 바람직하다고 할 수 있다.

다음과 같이 변수를 선언하고 생각을 시작하자.

  • \(n\) 명의 지원자가 있다.
    • 최고의 지원자를 \(\alpha\)라 하자.
    • 살펴보기 그룹을 \(\beta\)라 하자.
  • \(r\) 전략 : \(r\) 명째부터 커트라인 점수를 넘어서는 최초의 지원자를 합격시킨다.
    • \(r - 1\) 명까지 살펴보고 커트라인 점수를 정한다.
    • 즉, 살펴보기 그룹 \(\beta\)는 \(r - 1\) 명이다.
  • 지원자가 \(n\)명일 때 \(r\) 전략의 성공 확률을 \(P(r)\) 이라 하자.
    • 즉, \(n\)명 중 \(A\)가 채용될 확률을 \(P(r)\) 이라 한다.

이에 대해 다음과 같이 정리할 수 있을 것이다.

r 전략의 성공 확률 =
    α가 1등으로 면접볼 때 r 전략의 성공 확률
  + α가 2등으로 면접볼 때 r 전략의 성공 확률
  + α가 3등으로 면접볼 때 r 전략의 성공 확률
  + ...
  + α가 n등으로 면접볼 때 r 전략의 성공 확률

그런데 \(\alpha\)가 살펴보기 그룹 \(\beta\)안에 있다면 전략은 무조건 실패하므로, \(\alpha\)가 면접을 보는 순서가 \(r\)보다 작은 경우는 생각할 필요가 없다.

따라서 다음과 같이 줄일 수 있다.

r 전략의 성공 확률 =
    α가 r등으로 면접볼 때 r 전략의 성공 확률
  + α가 r + 1등으로 면접볼 때 r 전략의 성공 확률
  + α가 r + 2등으로 면접볼 때 r 전략의 성공 확률
  + ...
  + α가 n등으로 면접볼 때 r 전략의 성공 확률

그렇다면 \(r\) 전략의 성공 확률 \(P(r)\)은 다음과 같을 것이다.

\[\begin{align} P(r) & = \sum_{i = r}^{n}P(\text{A가 i 번째 순서} \cap \text{i 번째 지원자를 합격시킴}) \\ & = \sum_{i = r}^{n}P(\text{A가 i 번째 순서}) \times P(\text{i 번째 지원자를 합격시킴}) \\ & = \sum_{i = r}^{n}P(\text{A가 i 번째 순서}) \times P(\text{i보다 먼저 면접을 보는 지원자들 중 최고 점수를 가진 지원자가} \beta \text{에 있음}) \\ & = \sum_{i = r}^{n}\frac{1}{n} \times \frac{r - 1}{i - 1} \\ & = \frac{r - 1}{n}\sum_{i = r}^{n}\frac{1}{i - 1} \end{align}\]

이제 성공 확률이 최대가 되게 하는 \(r\)의 값을 구해보자.

일단 다음과 같이 정의한다.

  • \(\lim_{n \to \infty}n\)  
  • \(x = \lim_{n \to \infty}\frac{r}{n}\)  
  • \(t = \lim_{n \to \infty}\frac{i}{n}\)  
  • \(dt = \lim_{n \to \infty}\frac{1}{n}\)  

그리고 식을 다음과 같이 조작하면 \(P(x) = −x \ln (x)\) 임을 알 수 있다.

\[\begin{align} P(x) & = \lim_{n\to\infty}\frac{r - 1}{n}\sum_{i = r}^{n}\frac{1}{i - 1} \\ & = \lim_{n\to\infty}\frac{r}{n}\sum_{i = r}^{n}\frac{1}{i} \\ & = x\lim_{n\to\infty}\sum_{i = r}^{n}\frac{n}{i} \times \frac{1}{n} \\ & = x\lim_{n\to\infty}\sum_{i = r}^{n}\frac{n}{i} dt \\ & = x \int_{x}^{1}\frac{1}{t}dt \\ & = −x \ln (x) \\ \end{align}\]

마지막으로 \(P(x)\)이 최대가 되게 하는 \(x\)의 값을 구하기 위해 미분하여 근을 구하면 \(\frac{1}{e}\) 가 나온다.

그런데 \(x = \lim_{n \to \infty} \frac{r}{n}\) 이므로,

무수히 많은 \(n\) 명의 지원자가 있을 때 \(\alpha\)를 채용할 확률을 최대화하려면 \(n \times \frac{1}{e}\) 명의 지원자를 살펴보고 커트라인을 정해야 한다는 결론이 나온다.

한편, \(P(\frac{1}{e}) = - \frac{1}{e} \times \ln(\frac{1}{e}) = \frac{1}{e}\) 이므로, 전체 지원자의 \(\frac{1}{e}\)를 살펴보는 전략을 따를 때 \(\alpha\)를 고용할 확률 또한 \(\frac{1}{e}\) 가 된다.

참고로 \(\frac{1}{e}\)의 값은 다음과 같다.

\[\frac{1}{e} = 0.3678794411714...\]

응용

비서 문제의 해법은 시간에 대해서도 응용할 수 있다.

가령 자동차를 주차할 곳을 탐색하는 데에 10분 정도를 사용할 수 있는 상황이라면

  • 3분 정도 근처를 돌아보며 살펴본 다음
  • 이전까지 살펴본 곳들보다 더 나은 장소가 나왔을 때 주차를 하면 된다.

같은 방식으로, 자취방을 보러 다닐 때나 쇼핑몰에서 적당한 장갑을 찾을 때 등에도 응용할 수 잇다.

함께 읽기

  • [[/problem/miss-all-prizes-probability]]{n개의 제비뽑기에 n번 도전}