[5. 배열] 5.12 오프라인 데이터 샘플 구하기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

---

Q 5.12 오프라인 데이터 샘플 구하기

서로 다른 원소로 이루어진 배열과 부분 집합의 크기가 주어졌을 때, 주어진 크기의 부분 집합을 반환하는 알고리즘을 작성하라. 단, 모든 부분 집합이 생성될 확률은 같아야 한다. 입력 배열을 통해 부분 집합의 결과를 반환하시오.

---

같은 생성 확률의 부분 집합을 만들기 위해서는 다음과 같은 과정을 진행할 예정이다.
0. 배열의 이름은 A , k는 부분집합의 크기, n은 임의로 생성된 숫자 라고하자.
1. 숫자 생성기를 통하여 (0~k) 의 숫자를 임의로 생성한다. 
2. A[0]과 (1.에서 생성된 임의의 숫자 n)의 위치 A[n]과 swap한다.
3. 숫자 생성기를 통하여 (1~k)의 숫자를 임의로 생성.
4. A[1]과 3.에서 생성된 임의의 숫자 n의 위치 A[n]과 swap한다. 
5. A[2]와 ......을 반복하여 A[0]부터 A[k-1]번 까지의 고정된 k개의 원소의 집합을 구한다.

위 내용의 코드와 결과는 다음과 같다.

공간 복잡도 O(1), 시간 복잡도 O(k), k=부분집합의 크기

main

실행마다 다른 결과가 나옴