공부
-
문제 풀이공부 2023. 2. 17. 22:47
1. iterator를 이용해서 배열을 순차적으로 한번만 돎, random access X 배열의 길이는 알려지지 않았다. 이 중 n개를 뽑아야 하는데 배열의 길이를 m이라고 한다면 배열 모든 원소를 같은 확률인 n/m의 확률로 뽑아야 함. 메모리의 용량은 n개의 원소들을 저장할 수 있는 배열 하나이다. n=1인 경우부터 시작 iterator 순회하면서 1개를 배열에 투입. 2부터 iterator 마지막까지 1/n+1 ... 1/n+k의 확률로 뽑아서 배열에 있는 수와 변경하거나 1-(1/n+1), ... 1-(1/n+k) 의 확률로 뽑히지 않거나 계산한다. 모든 원소의 뽑힐 확률이 1/m = n/m으로 동일하다 n의 일반적인 경우에 대해서 이야기 해보자 마찬가지로 n개의 원소에 대해서 무조건 투입하고,..