비서 문제

요약

• 그냥 재밌는 내용

본문

• 문제

여러분은 인사 담당자이고, 현재 한 명의 비서를 뽑아야 하는 상황입니다. 총 n 명의 지원자가 지원을 했으며, 각 지원자는 서로 다른 적합도를 보입니다. 다만, 면접을 진행하기 전까지 여러분은 지원자의 적합도를 파악할 수 없습니다. 면접은 한 사람씩 진행되고, (야박하지만) 그 자리에서 당락을 결정해 줍니다. 
즉, 현재 면접을 보는 사람을 떨어 뜨리면 다시 이 사람을 부를 수 없고, 반대로 합격을 시키면, 이후의 지원자는 면접을 보지 못합니다. 이런 상황에서 여러분의 목표는 만약 지원자가 균등한 확률로 일렬로 배치되었다고 했을 때 가장 적합도가 높은 지원자를 합격시키는 것입니다.

• 해결 방식
  • 정답 전략(고전 secretary problem, n명, 순서 랜덤, 목표=“진짜 1등 뽑기”)은:
    • 앞에서 전체의 약 1/e ≈ 0.37 만큼은 → 무조건 탈락시키고 → 순위만 관찰해서 누가 지금까지 1등인지 기억한다.
  • 그 다음부터는 → 지금까지 나온 사람들 중 1등보다 더 좋은 사람이 나오면 바로 채용 → 끝까지 그런 사람이 없으면 마지막 사람 채용.*

해결 방법

- 지원자 수: n명
- 순서는 완전 랜덤 (각 순열 확률 동일)
- 우리는 사람을 **앞에서부터 한 명씩** 본다.
- 한 번 지나치면 그 사람은 **다시 뽑을 수 없다.**
- 목표: **전체 후보 중 “진짜 1등”을 뽑을 확률을 최대화하는 전략** 찾기.