C++로 배열의 모든 부분집합 XOR 합 구하기

이 문제에서는 n개의 숫자로 이루어진 배열 arr[]가 주어집니다. 우리의 목표는 배열에서 만들 수 있는 모든 부분집합의 XOR 값을 모두 더한 합을 구하는 프로그램을 작성하는 것입니다.

기본 아이디어는 다음과 같습니다. 먼저 배열의 모든 부분집합을 찾고, 각 부분집합에 포함된 원소들의 XOR 값을 계산한 뒤, 이를 sum 변수에 누적합니다.

문제 이해를 위한 예시

입력: arr[] = {5, 1, 4}
출력: 20

각 부분집합의 XOR 값:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0

XOR 합 = 5 + 1 + 4 + 4 + 1 + 5 = 20

단순한 접근 방법

가장 직관적인 해결책은 반복문을 사용해 배열의 모든 부분집합을 생성하고, 각 부분집합마다 원소들의 XOR을 계산하여 합을 갱신한 후 최종 결과를 반환하는 것입니다.

그러나 이 방법은 비효율적입니다. 배열의 크기가 n일 때 부분집합의 개수는 2^n개이므로, n이 커질수록 시간 복잡도가 지수적으로 증가하게 됩니다.

효율적인 접근 방법: XOR의 성질 활용

XOR 연산의 비트 단위 성질을 이용하면 O(n) 시간 안에 답을 구할 수 있습니다.

핵심 원리는 다음과 같습니다. 어떤 비트 위치가 배열 내 하나라도 원소에서 설정(set)되어 있다면, 전체 부분집합 중 정확히 절반인 2^(n-1)개의 부분집합에서 해당 비트가 XOR 결과에 기여합니다. 따라서 각 설정된 비트의 기여도는 (비트값 × 2^(n-1))이 됩니다.

이를 정리하면 다음 공식이 성립합니다:

모든 부분집합의 XOR 합 = (배열 전체 원소의 OR 값) × 2^(n-1)

즉, 배열의 모든 원소에 대해 OR 연산을 수행한 뒤, 그 결과에 2^(n-1)을 곱하면 됩니다.

구현 예제

위 해결 방법의 동작을 보여주는 C++ 프로그램입니다:

#include <iostream>
#include <math.h>
using namespace std;

int subSetXORSum(int arr[], int n) {
    // 배열의 모든 원소에 대해 OR 연산 수행
    int bitOR = 0;
    for (int i = 0; i < n; ++i)
        bitOR |= arr[i];
    // OR 값에 2^(n-1)을 곱해 반환
    return (bitOR * pow(2, n - 1));
}

int main() {
    int arr[] = {1, 5, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "모든 부분집합의 XOR 합은 " << subSetXORSum(arr, size);
    return 0;
}

실행 결과

모든 부분집합의 XOR 합은 20

복잡도 분석

시간 복잡도: O(n) — 배열을 한 번만 순회하여 OR 값을 계산합니다.
공간 복잡도: O(1) — 추가적인 저장 공간이 필요하지 않습니다.

이처럼 XOR의 비트 연산 성질을 활용하면, 지수적인 완전 탐색 없이도 선형 시간에 문제를 해결할 수 있습니다.