동전 뒤집기 원리로 무작위 부분집합을 만드는 C++ 프로그램

이 글에서는 동전 뒤집기(Coin Flipping) 개념을 응용하여 주어진 집합에서 무작위 부분집합(Random Subset)을 생성하는 C++ 프로그램을 소개합니다.

동전 뒤집기는 앞면과 뒷면이 나올 확률이 각각 50%인 난수 발생과 같습니다. 이를 집합의 각 원소에 적용하면, 동전이 '앞면'에 해당할 때만 해당 원소를 부분집합에 포함시키는 방식으로 자연스럽게 무작위 부분집합을 만들 수 있습니다.

알고리즘

시작
    배열에 담을 원소들을 입력받는다.
    rand() 함수를 사용해 무작위 이진 시퀀스(0 또는 1)를 생성한다.
    동전 뒤집기처럼 0 또는 1이 무작위로 나오며,
    값이 1일 경우 해당 배열 원소를 출력한다.
끝

핵심 아이디어

각 원소마다 rand() % 2를 계산하면 0 또는 1이 나오는데, 이는 동전을 한 번 던져 뒷면(0) 또는 앞면(1)이 나온 것과 같습니다. 결과가 1이면 그 원소를 부분집합에 넣고, 0이면 제외합니다. 이 과정을 모든 원소에 대해 반복하면 됩니다.

예제 코드

#include<iostream>
#include<stdlib.h>
using namespace std;
int main() {
    int i, n;
    cout<<"\n원소의 개수를 입력하세요: ";
    cin>>n;
    int a[n];
    cout<<"\n";
    for(i = 0; i < n; i++) {
        cout<<i+1<<"번째 원소 입력: ";
        cin>>a[i];
    }
    cout<<"\n주어진 집합의 무작위 부분집합은 다음과 같습니다:\n\t { ";
    for(i = 0; i < n; i++) {
        if(rand()%2 == 1)
            cout<<a[i]<<" ";
    }
    cout<<"}";
    return 0;
}

실행 결과

원소의 개수를 입력하세요: 7
1번째 원소 입력: 7
2번째 원소 입력: 6
3번째 원소 입력: 5
4번째 원소 입력: 4
5번째 원소 입력: 3
6번째 원소 입력: 2
7번째 원소 입력: 1
주어진 집합의 무작위 부분집합은 다음과 같습니다:
{ 7 6 3 }

참고 사항

프로그램을 실행할 때마다 rand()가 반환하는 값이 달라지므로, 같은 입력을 넣어도 매번 다른 부분집합이 출력됩니다. 더 균등한 난수 분포가 필요하다면 srand(time(NULL))로 시드를 초기화하고, 최신 컴파일러 환경에서는 가변 길이 배열 대신 vector<int> 사용을 권장합니다.