C++로 배열의 모든 부분집합 곱의 합 구하기 – 효율적인 알고리즘과 예제 코드

문제 소개

이 문제에서는 N개의 숫자로 이루어진 배열 arr[]가 주어지며, 만들 수 있는 모든 부분집합에 대해 각 부분집합에 속한 원소들의 곱을 구한 뒤, 그 값들을 모두 더한 최종 합계를 계산하는 프로그램을 작성하는 것이 목표입니다.

문제 이해를 위한 예시

입력:

arr[] = {4, 5, 6}

출력:

209

설명 −

arr[]의 모든 부분집합: {4}, {5}, {6}, {4, 5}, {5, 6}, {4, 6}, {4, 5, 6}
곱의 합
= (4) + (5) + (6) + (4*5) + (5*6) + (4*6) + (4*5*6)
= (4) + (5) + (6) + (20) + (30) + (24) + (120)
= 209

방법 1: 브루트 포스(완전 탐색)

가장 단순한 접근 방식은 집합의 모든 부분집합을 생성하고, 각 부분집합에 포함된 원소들의 곱을 계산한 후 이를 모두 더하는 것입니다. 모든 부분집합을 순회할 때까지 이 과정을 반복하면 최종 합계를 얻을 수 있습니다.

아래 예제는 이 해결 방법이 동작하는 과정을 보여줍니다.

#include<iostream>
#include<math.h>
using namespace std;
int findSumProductSubset(int *arr, int set_length) {
    unsigned int size = pow(2, set_length);
    int sum = 0;
    int product;
    for(int counter = 1; counter < size; counter++) {
        product = 1;
        for(int j = 0; j < set_length; j++) {
            if(counter & (1<<j))
            product *= arr[j];
        }
        sum += product;
    }
    return sum;
}
int main() {
    int arr[] = {4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"모든 부분집합의 곱의 합은 "<<findSumProductSubset(arr, n);
}

출력

모든 부분집합의 곱의 합은 209

위 코드는 비트마스킹(counter의 각 비트)을 이용해 모든 부분집합을 하나씩 생성하므로 시간 복잡도가 O(2ⁿ × n)으로 지수적으로 증가합니다. 따라서 원소 개수가 조금만 커져도 실행 시간이 급격히 늘어나는 비효율적인 방법입니다.

방법 2: 패턴을 찾는 효율적인 접근

더 나은 성능을 위해서는 해답 속에서 규칙성(패턴)을 찾아내면 됩니다. 세 개의 숫자 x, y, z로 이루어진 집합을 살펴보겠습니다.

sum = x + y + z + xy + yz + xz + xyz
sum = x + xz + y + yz + xy + xyz + z + 1 − 1
sum = x(1+z) + y(1+z) + xy(1+z) + 1(z+1) − 1
sum = (x + y + xy + 1)(1 + z) − 1
sum = (x(1+y) + 1(1+y))(1+z) − 1
sum = (1 + x) * (1 + y) * (1 + z) − 1

이 결과를 일반화하면 다음과 같습니다. n개의 원소를 가진 집합에 대해,

sum = (1 + e₁) × (1 + e₂) × … × (1 + eₙ) − 1

즉, 각 원소에 1을 더한 값을 모두 곱한 뒤 1을 빼면 원하는 답이 됩니다. 이 방법은 배열을 한 번만 순회하면 되므로 시간 복잡도가 O(n)으로 매우 효율적입니다.

예제 코드

#include <iostream>
using namespace std;
int productOfSubsetSums(int arr[], int n) {
    int sum = 1;
    for (int i = 0; i < n; ++i)
    sum *= (arr[i] + 1);
    sum--;
    return sum;
}
int main() {
    int arr[] = {5, 6, 8, 9};
    int n = sizeof(arr)/sizeof arr[0];
    cout<<"가능한 모든 부분집합의 곱의 합은 "<<productOfSubsetSums(arr, n);
    return 0;
}

출력

가능한 모든 부분집합의 곱의 합은 3779

검산해 보면, 배열 {5, 6, 8, 9}에 대해 (5+1) × (6+1) × (8+1) × (9+1) − 1 = 6 × 7 × 9 × 10 − 1 = 3779로 실제 출력과 일치합니다.

두 가지 방법 비교

마무리

부분집합의 곱의 합 문제는 겉보기에는 완전 탐색이 필요해 보이지만, 수학적 패턴을 발견하면 선형 시간에 해결할 수 있습니다. 실제 코딩 테스트나 알고리즘 문제 풀이에서는 (1+원소)의 누적 곱에서 1을 빼는 공식 기반 접근을 사용하는 것이 좋습니다.