처음 n개의 자연수로 이루어진 집합의 모든 부분집합 합 구하기 (C 코드 예제)

부분집합이란 무엇인가?

집합(Set)은 여러 데이터 요소를 하나로 묶어 놓은 자료구조입니다. 어떤 집합 B의 모든 원소가 집합 A에 속해 있다면, B를 A의 부분집합(subset)이라고 부릅니다. 예를 들어 A = {1, 2, 3}이라면 {1}, {2, 3} 등은 모두 A의 부분집합입니다.

문제 정의

이번 글에서 다룰 문제는 처음 n개의 자연수(1부터 n까지)로 이루어진 집합에 대해, 만들 수 있는 모든 부분집합의 원소를 전부 더한 총합을 구하는 것입니다. 즉, 가능한 모든 부분집합을 나열하고, 각 부분집합에 포함된 숫자들을 모두 합산해야 합니다.

예시로 살펴보기

n = 3인 경우를 가정해 보겠습니다.

집합 = {1, 2, 3}
만들 수 있는 부분집합 = { {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }

각 부분집합의 원소를 모두 더하면 다음과 같습니다.

합계 = 1 + 2 + 3 + (1+2) + (1+3) + (2+3) + (1+2+3) = 24

규칙 찾기: 왜 24가 나올까?

위 결과를 원소별로 다시 정리해 보면 흥미로운 패턴이 드러납니다. 각 숫자가 부분집합 안에서 등장하는 횟수를 세어 보면, 1은 네 번, 2는 네 번, 3 역시 네 번 등장합니다.

합계 = (1+1+1+1) + (2+2+2+2) + (3+3+3+3)
     = 4 × (1 + 2 + 3)
     = 4 × 6
     = 24

수학적 공식 유도

핵심 원리는 크기가 n인 집합에서 각 원소는 정확히 2^(n-1)개의 부분집합에 포함된다는 사실입니다. 특정 원소를 부분집합에 넣거나 넣지 않는 경우의 수를 생각하면, 나머지 n-1개 원소에 대해 자유롭게 선택할 수 있으므로 2^(n-1)가 됩니다.

따라서 모든 부분집합의 원소 총합은 다음 공식으로 깔끔하게 표현됩니다.

총합 = 2^(n-1) × (1 + 2 + ... + n) = 2^(n-1) × n(n+1)/2

앞선 예시로 검증해 보면, n = 3일 때 2² × (3 × 4 / 2) = 4 × 6 = 24로 실제 결과와 일치합니다. 덕분에 부분집합을 하나씩 생성하지 않고도 O(log n) 시간 만에 답을 구할 수 있습니다.

C 언어 구현 예제

n이 커지면 결과값이 매우 빠르게 증가하므로, 실제 구현에서는 보통 큰 수 오버플로를 막기 위해 모듈러 연산(예: 10⁹ + 7)을 함께 사용하고, 거듭제곱은 분할 정복 기법으로 빠르게 계산합니다.

#include <stdio.h>

#define MOD 1000000007LL

// 분할 정복으로 x^y % MOD를 계산하는 함수
long long power(long long x, long long y) {
    long long res = 1;
    x %= MOD;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return res;
}

int main() {
    int n = 3; // 처음 n개의 자연수
    long long total = (long long)n * (n + 1) / 2; // 1 + 2 + ... + n
    long long ans = power(2, n - 1) * (total % MOD) % MOD;
    printf("모든 부분집합의 합은 %lld 입니다\n", ans);
    return 0;
}

실행 결과

모든 부분집합의 합은 24 입니다

시간 복잡도

거듭제곱을 지수를 절반씩 줄여가며 계산하므로 전체 시간 복잡도는 O(log n)입니다. 부분집합을 직접 열거하는 O(n × 2ⁿ) 방식과 비교하면 압도적으로 효율적입니다.