Knuth의 Method

Knuth의 방법: 무작위로 하나를 선택하는 알고리즘
Knuth의 방법은 입력 데이터(여기서는 단어들)를 배열이나 리스트에 저장하지 않고도, 입력된 데이터 중 하나를 균등한 확률로 무작위로 선택할 수 있도록 설계된 알고리즘입니다.

1. 첫 번째 단어를 읽었을 때는 무조건 그 단어가 "챔피언(champion)"이 됩니다.
   (아직 다른 선택지가 없기 때문입니다.)

2. 두 번째 단어를 읽었을 때, 이 단어가 챔피언이 될 확률은 $\frac{1}{2}$입니다.

3. 세 번째 단어를 읽었을 때, 이 단어가 챔피언이 될 확률은 $\frac{1}{3}$입니다.

   • 확률 $\frac{1}{3}$로 새로운 단어를 챔피언으로 선택합니다.
   • 실패하면 기존 챔피언을 유지합니다.

4. 이 과정을 반복하면서 i번째 단어를 읽을 때마다 해당 단어를 챔피언으로 선택할 확률을 $\frac{1}{i}$로 계산합니다.

5. 모든 단어를 읽은 뒤, 최종적으로 남아있는 챔피언이 선택된 단어가 됩니다.

무슨 말이세요..