문제 개요
n개의 숫자로 이루어진 배열 arr[]가 주어졌을 때, 배열의 모든 부분 배열(subarray)에 대한 XOR 값의 합계를 구하는 것이 이번 문제의 목표입니다.
부분 배열이란 원본 배열에서 연속된 요소들로 이루어진 배열을 의미합니다. 따라서 주어진 배열에서 만들 수 있는 모든 부분 배열을 찾고, 각 부분 배열의 요소들을 XOR 연산한 뒤, 그 결과값들을 모두 더하면 됩니다.
예제로 이해하기
입력: arr[] = {5, 1, 4}
출력: 19
설명: 배열의 모든 부분 배열에 대한 XOR 값은 다음과 같습니다.
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5, 1} = 5 ^ 1 = 4
XOR {1, 4} = 1 ^ 4 = 5
XOR {5, 1, 4} = 5 ^ 1 ^ 4 = 0
합계 = 5 + 1 + 4 + 4 + 5 + 0 = 19단순한 접근 방법
가장 직관적인 방법은 중첩 반복문을 사용해 배열의 모든 부분 배열을 하나씩 생성하고, 각 부분 배열의 요소들을 XOR 연산한 후 그 값을 합계 변수에 누적하는 것입니다.
하지만 이 방법은 여러 겹의 반복문이 필요해 시간 복잡도가 최소 O(n²) 이상으로 증가합니다. 배열의 크기가 커질수록 연산량이 급격히 늘어나므로 실무에서는 비효율적입니다.
효율적인 접근 방법 ①: 프리픽스(Prefix) XOR 배열
XOR 연산의 성질을 활용하면 부분 배열의 XOR 값을 빠르게 구할 수 있습니다. 먼저 인덱스 i까지의 모든 요소를 XOR한 값을 저장하는 프리픽스 배열을 만듭니다.
prefixXOR[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]
이 배열을 이용하면 인덱스 i부터 j까지 구간의 XOR 값을 상수 시간(O(1))에 계산할 수 있습니다.
XOR(i..j) = prefixXOR[j] ^ prefixXOR[i-1] (i > 0일 때)
XOR(i..j) = prefixXOR[j] (i = 0일 때)
효율적인 접근 방법 ②: 비트별 기여도 계산
더 나아가, 각 비트 자리를 독립적으로 고려하는 방법도 있습니다. XOR 연산에서 특정 비트가 결과에 1로 나타나려면 해당 구간 내에서 그 비트가 설정된(set) 요소의 개수가 홀수여야 한다는 성질을 이용합니다.
- 각 비트 위치(i = 0 ~ 29)에 대해 배열을 순회하며, 그 비트가 포함된 요소가 홀수 번 등장하는 구간의 개수를 셉니다.
- 해당 개수에 비트 가중치(2i)를 곱해 결과에 누적합니다.
이렇게 하면 전체 시간 복잡도를 O(n × 비트 수)로 줄일 수 있어 배열이 클 때 특히 효과적입니다.
구현 예제
아래는 위에서 설명한 솔루션의 동작을 보여주는 C++ 프로그램입니다.
#include <iostream>
using namespace std;
int calcSubArrayXORSum(int arr[], int n) {
int sum = 0;
int multiplier = 1;
for (int i = 0; i < 30; i++) {
int oddCount = 0;
bool isOdd = 0;
for (int j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) > 0)
isOdd = (!isOdd);
if (isOdd)
oddCount++;
}
for (int j = 0; j < n; j++) {
sum += (multiplier * oddCount);
if ((arr[j] & (1 << i)) > 0)
oddCount = (n - j - oddCount);
}
multiplier *= 2;
}
return sum;
}
int main() {
int arr[] = { 3, 8, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all subarrays is "<<calcSubArrayXORSum(arr, n);
return 0;
}
실행 결과
Sum of XOR of all subarrays is 46
배열 {3, 8, 13}의 모든 부분 배열({3}, {8}, {13}, {3,8}, {8,13}, {3,8,13})의 XOR 값은 각각 3, 8, 13, 11, 5, 6이며, 이를 모두 더한 46이 출력됩니다.
마무리
브루트 포스 방식으로는 O(n²) 이상의 시간이 필요하지만, 프리픽스 XOR 배열이나 비트별 기여도 계산 기법을 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다. XOR 연산의 비트 단위 성질을 이해하면 이런 유형의 부분 배열 문제를 쉽게 최적화할 수 있습니다.