각 부분 집합 원소들의 합의 개수 구하기

각 부분 집합 원소들의 합의 개수란 무엇인가?

한 집합에는 여러 개의 부분 집합이 존재하기 때문에 원소가 숫자로 되어 있는 집합의 부분 집합마다 원소들의 합을 구할 수 있습니다. 중복된 합은 1개로 세어 이러한 합들의 개수를 구하는 문제입니다.

부분 집합

부분 집합의 개수는 원소의 개수 n으로 표현할 수 있습니다. 2^n개입니다. 2^n개 모두 각각의 원소들의 합을 모두 구해야 하기 때문에 무수히 큰 수는 되지 않고 간단히 원소의 개수가 4개로 가정하고 예를 들어 봅시다.

{1,2,3,4}의 부분 집합은 다음과 같습니다.

공집합, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}

공집합의 원소의 합은 0으로 하고 각 부분 집합의 원소들의 합을 구하면 다음과 같고 중복된 수를 제외하면 총 11개의 중복되지 않은 각 부분 집합 원소들의 합을 구할 수 있습니다.

0,1,2,3,4,3,4,5,5,6,7,6,7,8,9,10

프로그램으로 부분 집합 만들기

부분 집합의 원소들의 합을 구하기 위해서는 부분 집합을 구해야 합니다. 이를 구하기 위해서는 {1,2,3,4}의 원소들을 비트 단위로 구분하여 &연산자를 통해 해당 원소가 존재하는 지 확인하여 부분 집합을 구할 수 있습니다. 아래의 코드를 보시면 이해가 쉬울 것입니다.

// k는 1부터 2^n까지이며 어떤 원소가 포함된 부분 집합들
for (k=0; k<(1<<4); k++) {

    // i는 어느 원소가 존재하는 지를 판단함
    for (i=0;i<4;i++) {

        // 해당 원소 존재
        if (k & (1<<i)==1) {
            // TODO
        }
    }
}

k가 0일 경우에 공집합을 의미하며 1인 경우에는 비트로 0001이며 {1, 2, 3, 4}의 경우에 k는 1이 존재하는 부분 집합 {1}을 의미합니다. 따라서 TODO 주석 부분에 원소를 저장를 저장하거나 원소를 바로 더해서 저장하여 각 부분 집합들의 원소의 합을 구할 수 있습니다.

프로그램에서의 원소가 존재하는 지를 판단하기

이처럼 원소가 존재하는지는 &연산자를 통해 알 수 있습니다. 이러한 작업을 아래와 같이 프로그램에서도 많이 사용됩니다.

#define A_FLAG 0x01
#define B_FLAG 0x02
#define C_FLAG 0x04

int main(){
    int flag = 3;

    if ((flag & A_FLAG) == 1){
        // TODO: if flag is A_FLAG
    }
    if ((flag & B_FLAG) == 1){
        // TODO: if flag is B_FLAG
    }
    if ((flag & C_FLAG) == 1){
        // TODO: if flag is C_FLAG
    }
    exit(0);
}