N개의 정수로 이루어진 배열과 Q개의 범위 쿼리가 주어졌을 때, 각 쿼리마다 해당 범위 안에 있는 모든 숫자의 최대 홀수 약수(greatest odd divisor)를 구한 후, 이 값들을 XOR 연산한 결과를 반환하는 문제입니다.
여기서 최대 홀수 약수란 어떤 수 N을 나눌 수 있는 가장 큰 홀수를 의미합니다. 예를 들어 6의 최대 홀수 약수는 3입니다.
입력: nums[] = { 3, 6, 7, 10 }, query[] = { { 0, 2 }, { 1, 3 } }
출력:
쿼리1: 7
쿼리2: 1
설명: nums 배열 각 원소의 최대 홀수 약수는 { 3, 3, 7, 5 } 입니다.
쿼리1은 인덱스 0, 1, 2의 XOR 값인 7을,
쿼리2는 인덱스 1, 2, 3의 XOR 값인 1을 반환합니다.문제 해결 접근 방법
단순 접근법
가장 기본적인 방법은 먼저 배열의 모든 원소에 대해 최대 홀수 약수를 구하고, 쿼리가 들어올 때마다 해당 범위 내 원소들을 하나씩 XOR 연산하여 결과를 반환하는 것입니다. 다만 이 방식은 쿼리 하나를 처리하는 데 O(N)의 시간이 걸리므로, 쿼리 개수가 많아지면 비효율적이라는 단점이 있습니다.
효율적인 접근법: 누적 XOR(Prefix XOR) 배열 활용
더 효율적으로 문제를 해결하려면, 각 원소의 최대 홀수 약수를 담은 배열에 대해 누적 XOR(prefix XOR) 배열을 미리 만들어 두는 것이 좋습니다. 누적 XOR 배열이란 각 위치에 그 위치까지의 모든 이전 원소들의 XOR 값을 저장한 배열을 말합니다.
이렇게 준비해 두면 [L, R] 범위의 XOR 값은 prefix_XOR[R]과 prefix_XOR[L-1]을 XOR 연산한 값으로 즉시 계산할 수 있으며, 각 쿼리를 O(1) 시간에 처리할 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int main(){
int nums[] = { 3, 6, 7, 10 };
int n = sizeof(nums) / sizeof(nums[0]);
int prefix_XOR[n];
// 각 원소의 최대 홀수 약수를 저장하는 배열 생성
for (int i = 0; i < n; i++) {
// 홀수가 될 때까지 2로 계속 나눔
while (nums[i] % 2 != 1)
nums[i] /= 2;
prefix_XOR[i] = nums[i];
}
// prefix_XOR 배열을 누적 XOR 배열로 변환
for (int i = 1; i < n; i++)
prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i];
// 결과를 구할 쿼리 배열
int query[2][2] = {{0, 2}, {1, 3}};
int q = sizeof(query) / sizeof(query[0]);
// 각 쿼리의 결과 계산
for (int i = 0; i < q; i++){
if (query[i][0] == 0)
cout << prefix_XOR[query[i][1]] << endl;
else{
int result = prefix_XOR[query[i][1]] ^ prefix_XOR[query[i][0] - 1];
cout << result << endl;
}
}
return 0;
}
실행 결과
7
1
코드 설명
prefix_XOR배열을 만들어 각 원소의 최대 홀수 약수를 먼저 저장한 뒤, 이 배열을 누적 XOR 배열로 변환합니다.최대 홀수 약수는 해당 수를 2로 나눈 나머지가 1이 될 때까지 계속 2로 나누어 구합니다.
누적 XOR 배열은 배열을 순회하면서 현재 원소와 바로 이전 원소를 비트 XOR 연산하여 만듭니다.
쿼리의 결과는
prefix_XOR[R]과prefix_XOR[L-1]을 XOR 연산하여 구합니다. 왼쪽 인덱스가 0인 경우에는prefix_XOR[R]값 자체가 곧 답이 됩니다.
마무리
이번 글에서는 주어진 배열의 특정 범위 내 각 숫자의 최대 홀수 약수를 구해 XOR 연산하는 문제를 다뤘습니다. 각 원소의 최대 홀수 약수를 구하고 누적 XOR 배열을 활용하면, 여러 개의 범위 쿼리도 매우 빠르게 처리할 수 있습니다. 소개한 C++ 코드는 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.