최적화 (optimization) 문제는 주어진 조건에서 최적의 결과물을 만들 수 있는 (혹은 보상을 얻을 수 있는, 혹은 피해를 최소화할 수 있는 등등) 방법을 찾는 문제입니다. 수학, 컴퓨터과학 뿐만 아니라 공학, 나아가 사회과학에서도 다양하게 활용되고 연구되는 주제이기도 합니다. 최적화 문제에서 자주 언급되는 케이스로서 이른바 '비서 채용 문제 (secretaty selection problem)'라고 부르는 문제가 있습니다. 이 문제는 다음과 같습니다.
당신은 비서를 한 명 채용하기 위해 후보자들을 면접하려 합니다. 채용하려는 후보는 N명 있습니다.
1. 면접은 1:1로 한 명씩 차례대로 합니다.
2. 면접 이후, 후보자에게 바로 합/불을 알려줘야 합니다.
3. 불합격한 후보자는 다시 부를 수 없습니다.
4. 특정 후보자에게 합격을 통보하는 순간 뒤에 몇 명의 후보자가 있든, 면접을 종료합니다.
N명의 후보 중, 분명 최고의 자질을 가진 후보가 포함되어 있을텐데, 그...