알고리즘 & 확률/Secretary (1) 썸네일형 리스트형 비서 문제 (Secretary Problem) 여러분이 다음 뽑기 게임에 참가했다고 가정해 봅시다. 안을 볼 수 없는 상자가 여러분 앞에 놓여 있습니다. 여러분은 상자 안에 총 \(n\) 개의 공이 들어 있다는 것과, 공에는 서로 다른 숫자가 적혀 있다는 것을 알고 있습니다. 이제 여러분은 상자에서 공을 하나씩 무작위로 뽑고 공의 숫자를 확인할 것입니다. 만약 숫자가 마음에 든다면 여러분은 이 공을 선택할 수 있고, 만약 마음에 들지 않는다면 이를 버리고 새 공을 뽑을 수 있습니다. 다만 한 번 버린 공은 다시 주울 수 없죠. 가장 큰 숫자가 적힌 공을 선택해야 뽑기 게임에서 이긴다고 할 때, 과연 여러분은 어떤 전략을 취해야 할까요? 이 문제는 1950-60년대 여러 수학자들과 통계학자들 사이에서 매우 깊이 연구되었던 비서 문제(secretary .. 이전 1 다음
