전체확률의정리 썸네일형 리스트형 Reservoir Sampling Algorithm - 순차적으로 한 번에 하나의 샘플만 볼 수 있고 전체 샘플 개수를 모르는 상황에서 무작위 추출을 하는 방법 왜 이런 설정에서 무작위 추출을 할 수 있는 것이 중요할까? 오늘은 확률 기법 수업의 숙제로 받은 연습문제를 풀다가 재미있는 알고리즘을 알게 되어 글을 쓰게 되었습니다. 보통 random sampling(무작위 추출)과 관련된 문제를 풀 때면 우리는 주머니에 들은 여러 개의 공 중에 하나의 공을 뽑는 것처럼 모든 샘플을 모아 두고 거기서 하나를 공평하게 뽑는 상상을 합니다. 하지만 항상 모든 샘플에 대한 접근이 가능한 것도 아니고 샘플의 개수가 총 몇 개인지도 모르는 경우도 있습니다. 예를 들어, 메모리가 제한적인 기기를 생각해보지요. 모든 샘플을 다 저장해둔 후 총샘플의 개수를 알고 각각의 샘플을 1/(샘플의 총 개수)의 확률로 무작위 추출을 하려면 샘플의 개수만큼 많은 메모리가 필요합니다. 하지만 메.. 더보기 이전 1 다음
