[5. 배열] 5.15 임의의 부분 집합 만들기
[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다.
문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.
Q 5.15 임의의 부분 집합 만들기
양의 정수 n과 크기 k(k<n)가 주어졌을 때, <0,1,2,....,n-1>의 집합에서 크기가 k인 부분 집합을 반환하는 프로그램을 작성하라. 부분 집합은 배열로 표현하고, 모든 부분 집합뿐만 아니라 배열 내의 모든 순열 또한 같은 확률로 나타나야 한다.
해시 테이블 H 를 이용하여 다음과 같이 표현한다.
H의 초기값은 <0,1,2,3,...,n-1>이라고 하자.
위치번호i 가 H안에 있다면 이 값은 배열A[i]에 저장되어있는 값이고, H안에 없다면 A[i]=i를 의미한다고 하자.
예를들어 n=100, k=4 라고 하자. 첫 번째 반복에서 임의의 숫자 28이 선택 되었다고 하면 다음과 같다.
H(0,28), (28,0) 이는 A[28] = 0, A[0] = 28 과 같다. 나머지는 모두 A[i] = i 이다.
두번째 숫자 42가 선택 되었다고 하면 다음과 같다.
H(0,28),(28,0),(1,42),(42,1)
세번째 다시 28이 선택 되었다고 하면 다음과 같다.
H(0,28),(28,0),(1,42),(42,1),(2,0)
마지막으로 62가 선택 되면 다음과 같다.
H(0,28),(28,0),(1,42),(42,1),(2,0),(3,64),(64,3)
따라서 임의의 부분 집합은 0~3 값인 <28,42,0,64> 가 된다.
해당 소스코드와 결과는 다음과 같다.
