[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다.
문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.
Q 5.14 임의의 순열 계산하기
<0,1,....,n-1>로 이루어진 임의의 순열을 동일한 확률로 만들어 내는 알고리즘을 작성하라.
숫자를 같은 확률로 반환하는 임의의 숫자 생성기가 주어졌다고 가정해도 되며, 이 생성기를 가능하면 적게 호출하도록 하자.
문제 5.12 오프라인 데이터 샘플 구하기에서 사용한 방법을 이용하려고 한다.
[5. 배열] 5.12 오프라인 데이터 샘플 구하기
[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌시간복잡도와 공간복잡도
msugi.tistory.com
문제 5.12를 이용하면 반복마다 배열을 부분 순열과 남아있는 값으로 나눌 수 있다.
반환되는 부분 집합이 항상 같다고 하더라도 모든 n!개의 가능한 순열이 같은 확률로 선택된다.
소스코드와 결과는 다음과 같다.
'C++ 학습 > C++ 코딩인터뷰[5장]' 카테고리의 다른 글
| [5. 배열] 5.16 균등하지 않은 임의의 숫자 생성하기 (0) | 2025.01.22 |
|---|---|
| [5. 배열] 5.15 임의의 부분 집합 만들기 (0) | 2025.01.15 |
| [5. 배열] 5.13 온라인 데이터 샘플 구하기 (0) | 2025.01.15 |
| [5. 배열] 5.12 오프라인 데이터 샘플 구하기 (0) | 2025.01.15 |
| [5. 배열] 5.11 다음 순열 구하기 (0) | 2025.01.15 |
