Jon Bentley가 쓴
Programming Pearls 12장. SAMPLE PROBLEM을 정리한 글이다.
문제여론 조사 기관에서는 N 명의 사람 중에서 M 명의 사람을 무작위로 추출하여 설문 조사를 한다.
M < N
N 명의 사람엔 0부터 시작하는 일련번호가 부여되어 있다. N을 5라고 가정하면 다음과 같다.
0 강백호
1 서태웅
2 채치수
3 정대만
4 송태섭
M이 2라면 이 중 동일한 확률로 2명을 추출해야 한다.
이는 0에서 N 사이에서 M 개의 숫자를 동일한 확률로 무작위로 추출하는 것에 다름아니다.
* 이 문제를 해결하는데 다음 2 함수를 사용할 수 있다.
bigrand : m 혹은 n 보다도 클 수 있는 정수를 무작위로 반환한다.
randint(i, j) : i에서 j 사이에 포함되어 있는 정수를 무작위로 반환한다.
솔루션 1select = m
remaining = n
for i = [0, n)
if (bigrand() % remaining) < select
print i
select--
remaining--
* 추출된 숫자는 m 보다 많을 수도 m 보다 적을 수도 없다. 강조한 부분을 주의 깊게 보면 이를 파악할 수 있다.
일련번호가 0인 강백호가 선택될 확률은 2 / 5이지만 이 후에 있는 사람들이 선택될 확률은 앞 결과에 영향을 받는다. 예를 들어 강백호가
선택되면 일련번호가 1인 서태웅이 선택될 확률은 1 / 4이고, 강백호가 선택되지 않으면 서태웅이 선택될 확률은 2 / 4이다.
그러나 전체적으로는 서태웅이 추출될 확률도 2 / 5이다.
서태웅이 추출될 확률
= 강백호가 추출될 확률 (2 / 5) * 1 / 4 + 강백호가 추출되지 않을 확률 (3 / 5) * 2 / 4
= 2 / 20 + 6 / 20
= 2 / 5
이를 C++로 구현하면 다음과 같다.
void genknuth(int m, int n)
{
for (int i = 0; i < n; i++)
if ((bigrand() % (n - i) < m) {
cout << i << "\n";
m--:
}
}
솔루션 2set에 난수를 담는 방법도 있다.
* set에는 동일한 값이 들어 갈 수 없다.
initialize set S to empty
size = 0
while size < m do
t = bigrand() % n
if t is not in S
insert t into S
size++
print the elements of S in sorted order
C++ STL을 이용하여 구현하면 다음과 같다.
void gensets(int m, int n)
{
set<int> S;
while (S.size() < m)
S.insert(bigrand() % n);
set<int>::iterator i;
for (i < S.begin(); i != S.end(); ++i)
cout << *i << "\n";
}
솔루션 3n 개 크기 배열을 만든 후에 이들의 위치를 무작위로 변경(swap)하고 처음 m 개를 선택하는 방법도 있다. 화투나 포카에서 카드를 섞는 것(shuffle)과 유사하다.
for i = [0, n)
swap(i, randint(i, n - 1))
C++를 구현하면 다음과 같다.
void genshuf(int m, int n)
{
int i, j;
int *x = new int[n];
for (i = 0;; i < n; i++)
x[i] = i;
for (i = 0; i < m; i++) {
j = randint(i, n - 1);
int t = x[i]; x[i] = x[j]; x[j] = t;
}
sort(x, x + m)
for (i = 0; i < m; i++)
cout << x[i] << "\n";
}
개념 코드와는 다르게 m개 까지만 swap한다. (Ashley Shepherd와 Alex Woronow)
기타만약 n이 100만이고 m이 n - 10이라면 조금은 다르게 접근해야 한다. 이 경우에는 추출되지 않을 10개를 계산하는 것이 적합하다.
프로그래밍 혹은 문제 해결은 다음과 같이 진행된다.- Understand the Perceived Problem
- Specify an Abstract Problem
- Explore the Design Space
- Implement One Solution
- Retrospect
