[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다.
문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.
Q 5.13 온라인 데이터 샘플 구하기
실시간으로 패킷이 유입되는 상황에서 어떤 정수값 k가 주어졌을 때, k개의 임의의 패킷을 균일한 확률로 유지하는 알고리즘을 설계하라.
균일한 확률을 유지해야 하므로 다음과 같은 방법을 사용한다.
0. 배열의 이름은 A , k는 패킷의 크기라고하자.
1. 배열A를 <p,q,r,t,u,v> 라고 가정 하자.
2. k=2라고하면 앞에서부터 2개인 <p,q> 를 가지고 시작하자.
3. 다음 패킷을 읽어 r을 부분집합의 포함시킬 확률을 구하면 2/3이다.
4. 포함시키게 되면 p,q중에 하나를 같은 확률로 선택 하여 교환, 포함시키지 않으면 그대로 진행을 선택한다.
5. 위와 같은 방법으로 패킷이 늘어날때마다 2/4, 2/5 ... 와 같은 확률을 갖는다.
위 방법으로 작성한 코드와 결과는 다음과 같다.
'C++ 학습 > C++ 코딩인터뷰[5장]' 카테고리의 다른 글
| [5. 배열] 5.15 임의의 부분 집합 만들기 (0) | 2025.01.15 |
|---|---|
| [5. 배열] 5.14 임의의 순열 계산하기 (0) | 2025.01.15 |
| [5. 배열] 5.12 오프라인 데이터 샘플 구하기 (0) | 2025.01.15 |
| [5. 배열] 5.11 다음 순열 구하기 (0) | 2025.01.15 |
| [5. 배열] 5.10 배열 안의 원소로 순열 구하기 (0) | 2025.01.15 |
