[완전탐색/부분집합] 비트를 이용하여 모든 부분집합을 구하자!

부분 집합이란 전체의 집합에서 하나의 원소를 '고른다 / 안 고른다' 두 가지의 경우에 대해 살펴보는 것이므로 2^n 가지의 경우가 나옵니다.

이는 비트를 이용하면 굉장히 쉽게 구할 수 있습니다! 

왜냐하면 비트는 이진수이기 때문에, 하나의 자리수마다 고른다 (1) / 안 고른다(0)을 설정할 수 있기 때문입니다!

 
#include<stdlib.h>
#include<time.h>
#include<stdio.h>
 
int arr[10];
 
void print(int bit)
{
    int idx = 0;
    while (bit)
    {
        if (bit & 1)
        {
            printf("%d ", arr[idx]);
        }
        bit >>= 1;
        idx++;
    }
    printf("\n");
}
 
int main()
{
    srand(time(NULL));
 
    int t = 10;
    while (t--)
    {
        int len = rand() % 5 + 1;
 
        printf("nums : ");
        for (int i = 0; i < len; i++)
        {
            arr[i] = rand() % 10;
            printf("%d ", arr[i]);
        }
        printf("\n");
 
        printf("sub set\n");
 
        for (int i = 0; i < (1 << len); i++)
        {
            print(i);
        }
        printf("\n");
    }
 
    return 0;
}

우선, 만약 데이터의 개수가 5개라면 나올 수 있는 최대 경우는 11111가 됩니다.

즉, 1 << len 까지 i를 1씩 증가시키면, 모든 경우의 수를 확인할 수 있다는 것 입니다!

아래는 하나의 예시입니다.

000 공집합

001 2

010 6

011 2 6

100 8

101 2 8

110 6 8

111 2 6 8

참고로, int는 4 바이트 이기 때문에, 32비트로 이루어져 있습니다. 이는 비트를 32개 까지 저장할 수 있다는 의미 입니다.

만약 30개가 넘는 수의 데이터에 대해서 부분 집합을 구하고 싶다면 long long을 사용하는 것이 좋습니다.

하지만, 보통 시간 제한이 짧기 때문에 보통 30개가 넘는 데이터에 대한 부분 집합을 처리하는 일은 없습니다! 

시간 복잡도가 이고, 이기 때문에  이 됩니다. 정확하지는 않지만 반복문을 도는 것 만으로도 1초가 넘는 시간이 걸리기 때문이죠.

보통 문제는 3초 내외의 시간을 요구하는 경우가 많기 때문에 부분 집합을 이용하는 문제라면 int형 만으로도 가능할 것입니다.