최적화 (optimization) 문제는 주어진 조건에서 최적의 결과물을 만들 수 있는 (혹은 보상을 얻을 수 있는, 혹은 피해를 최소화할 수 있는 등등) 방법을 찾는 문제입니다. 수학, 컴퓨터과학 뿐만 아니라 공학, 나아가 사회과학에서도 다양하게 활용되고 연구되는 주제이기도 합니다. 최적화 문제에서 자주 언급되는 케이스로서 이른바 '비서 채용 문제 (secretaty selection problem)'라고 부르는 문제가 있습니다. 이 문제는 다음과 같습니다.

당신은 비서를 한 명 채용하기 위해 후보자들을 면접하려 합니다. 채용하려는 후보는 N명 있습니다.
1. 면접은 1:1로 한 명씩 차례대로 합니다.
2. 면접 이후, 후보자에게 바로 합/불을 알려줘야 합니다.
3. 불합격한 후보자는 다시 부를 수 없습니다.
4. 특정 후보자에게 합격을 통보하는 순간 뒤에 몇 명의 후보자가 있든, 면접을 종료합니다.

N명의 후보 중, 분명 최고의 자질을 가진 후보가 포함되어 있을텐데, 그 후보자를 찾기 위해서는 몇 번의 면접을 봐야 할까요? 문제를 쉽게 이해하기 위해 100명의 후보자가 있고, 최적의 후보자를 찾기 위해 100명다 면접을 보는 상황을 생각해 봅시다. 이 경우 우리는 최적의 후보를 뽑지 못 할 가능성이 매우 높다는 것을 쉽게 추측할 수 있습니다. 왜냐하면 100번째 후보까지 오는 동안, 99명의 후보자들에게는 불합격을 날렸을 것이기 때문입니다. 마지막 후보가 최적의 후보일 수도 있겠지만, 그것보다는 앞선 99명의 불합격자 속에 최적의 후보가 포함되었을 확률이 훨씬 높을 것입니다. 반대로 첫번째 후보자를 만나자마자 합격시키는 것 역시 최적의 후보를 찾기에는 좋은 방법이 아닙니다. 당연히 뒤에 기다리고 있는 99명의 후보자 pool에 최적의 후보가 포함되어 있을 확률이 높을 것이기 때문입니다. 따라서 우리는 첫번째도 아니고 끝번째도 아닌, 중간 어디쯤에서인가 면접을 마쳐야 할 것임을 예상할 수 있습니다. 관건은 그 최적의 멈춤 지점이 어디쯤인가에 대한 것입니다. 대충 ...