문제 정의
배열과 여러 개의 쿼리가 주어졌을 때, 각 쿼리마다 범위 (L, R)가 주어집니다. 이때 범위 내의 모든 원소와 x를 XOR한 값의 합이 최대가 되도록 하는 숫자 x를 찾는 것이 목표입니다. 예를 들어 다음과 같습니다.
입력 : A = {20, 11, 18, 2, 13}
세 개의 쿼리 (L, R) 쌍
1 3
3 5
2 4
출력 : 2147483629
2147483645
2147483645이 문제의 핵심 아이디어는 비트별 누적합(prefix count)입니다. 각 비트 위치(0~31)마다 배열의 앞부분부터 1이 등장한 횟수를 미리 계산해 두면, 임의의 범위 [L, R]에 포함된 1의 개수를 "R까지의 누적값에서 L−1까지의 누적값을 뺀 값"으로 상수 시간에 구할 수 있습니다.
풀이 접근 방법
XOR 연산의 성질상, 두 값의 특정 비트가 서로 다르면 결과 비트가 1이 됩니다. 따라서 합을 최대화하려면 가능한 한 많은 비트가 1이 되도록 x를 선택해야 합니다.
각 비트 위치에 대해 범위 내 숫자들의 1의 개수가 0의 개수보다 많다면, x의 해당 비트를 0으로 설정하는 것이 유리합니다. 다수의 숫자가 그 비트에서 1을 가지고 있으므로, x의 비트를 0으로 맞추면 XOR 결과에서 그 비트가 1이 되는 숫자가 더 많아져 전체 합이 커집니다. 이것이 바로 답을 최대화하는 원리입니다.
구현에서는 x를 231 − 1(모든 비트가 1)로 초기화한 뒤, 위 조건에 해당하는 비트만 1에서 0으로 토글하여 최종 답을 만듭니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647 // 2^31 - 1
int prefix[100001][32]; // 누적합 배열
void prefix_bit(int A[], int n){ // 각 비트별 1의 개수 누적합 계산
for (int j = 0; j < 32; j++) // 0번째 카운트는 0으로 두고 누적 배열은 인덱스 1부터 시작
prefix[0][j] = 0;
for (int i = 1; i <= n; i++){ // 누적 배열 생성
int a = A[i - 1]; // i번째 원소
for (int j = 0; j < 32; j++){ // 수가 2^32보다 작으므로 비트 0~31을 순회
int x = 1 << j; // 비트 순회용 마스크
if (a & x) // 해당 비트가 1이면 이전 카운트 + 1
prefix[i][j] = 1 + prefix[i - 1][j];
else
prefix[i][j] = prefix[i - 1][j];
}
}
}
int maximum_num(int l, int r){
int numberofbits = r - l + 1; // 범위 내 원소 개수, 즉 비트 개수
int X = MAX; // 모든 비트가 1인 최댓값으로 초기화
// 각 비트를 순회
for (int i = 0; i < 31; i++){
int x = prefix[r][i] - prefix[l - 1][i]; // 주어진 범위에서 1인 비트의 개수
if (x >= numberofbits - x){ // 1의 개수가 0의 개수보다 많거나 같은 경우
int currentbit = 1 << i; // x의 해당 비트를 토글하기 위한 마스크
X = X ^ currentbit; // 해당 비트를 1에서 0으로 변경
}
}
return X; // 정답 반환
}
int main(){
int n = 5, q = 3; // 배열의 원소 개수와 쿼리 개수
int A[] = { 210, 11, 48, 22, 133 }; // 배열의 원소들
int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // 주어진 쿼리들
prefix_bit(A, n); // 비트 누적 배열 생성
for (int i = 0; i < q; i++)
cout << maximum_num(L[i], R[i]) << "\n";
return 0;
}실행 결과
2147483629 2147483647 2147483629
코드 설명
먼저 prefix_bit 함수는 각 비트 위치별로 1의 개수에 대한 누적합을 계산합니다. 이 전처리 과정 덕분에 쿼리를 처리할 때마다 범위를 일일이 순회할 필요가 없어집니다. 즉, 이 문제의 가장 큰 병목이었던 쿼리 순회 문제를 누적 배열 하나로 해결한 것입니다.
maximum_num 함수에서는 범위 [l, r]에 포함된 원소 개수를 구한 뒤, 각 비트별로 1의 개수(prefix[r][i] − prefix[l−1][i])를 계산합니다. 만약 어떤 비트에서 1의 개수가 0의 개수보다 크거나 같다면, x의 해당 비트를 토글합니다. x는 231 − 1로 초기화되어 모든 비트가 1로 설정되어 있으므로, 이 토글 과정을 거치면 조건에 맞는 비트들이 0으로 바뀌고 최종적으로 원하는 답을 얻게 됩니다.
시간 복잡도는 전처리에 O(N × 32), 각 쿼리 처리에 O(32)가 소요되므로, 전체적으로 O((N + Q) × 32)입니다. 단순히 매 쿼리마다 범위를 순회하는 브루트포스 방식(O(Q × N × 32))에 비해 훨씬 효율적입니다.
결론
이번 글에서는 주어진 배열 범위에서 XOR 합이 최대가 되는 숫자를 찾는 문제를 다루었습니다. 비트별 누적합을 활용하면 각 쿼리를 상수 시간에 처리할 수 있다는 점이 핵심입니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.