알고리즘에서 '저수지 샘플링(Reservoir Sampling)'의 핵심 특징은?

해설

저수지 샘플링은 전체 데이터 크기 N을 미리 알 수 없는 스트림에서, O(k) 메모리만으로 k개의 균일 무작위 샘플을 추출합니다. i번째 원소가 선택될 확률은 항상 k/i로, 모든 원소가 최종적으로 같은 확률(k/N)로 선택됩니다.