이 문제에서는 n개의 요소로 이루어진 배열 arr[]과 정수 k가 주어집니다. 우리의 목표는 크기가 k인 부분 배열(subarray) 중에서 XOR 값이 가장 큰 값을 찾는 것입니다.
예제를 통해 문제를 자세히 살펴보겠습니다.
입력 예시
arr[] = {3, 1, 6, 2, 7, 9}, k = 3출력 결과
12
설명
크기가 k인 모든 부분 배열과 각 배열의 XOR 값을 계산하면 다음과 같습니다.
{3, 1, 6} = 4
{1, 6, 2} = 5
{6, 2, 7} = 3
{2, 7, 9} = 12계산된 값 중 가장 큰 값은 12이므로, 정답은 12가 됩니다.
해결 방법
방법 1: 단순 반복문 사용
가장 간단한 방법은 두 개의 반복문을 사용하는 것입니다. 첫 번째 반복문으로 배열을 순회하고, 두 번째 반복문으로 각 부분 배열 내 모든 요소의 XOR 값을 계산한 뒤, 그중 최댓값을 반환합니다. 이 방법은 직관적이지만 시간 복잡도가 O(n*k)로 비효율적일 수 있습니다.
방법 2: 슬라이딩 윈도우 기법 활용 (권장)
더 효율적인 접근 방식은 슬라이딩 윈도우(sliding window) 기법입니다. 핵심 아이디어는 다음과 같습니다.
먼저 인덱스 0부터 시작하는 크기 k의 부분 배열에 대한 XOR 값을 구합니다. 그다음 배열을 순회하면서 새로운 요소를 XOR에 추가하고, 윈도우에서 벗어나는 첫 번째 요소를 제거합니다.
여기서 삭제 작업은 XOR의 중요한 성질인 x ^ a ^ x = a 공식을 활용합니다. 즉, 같은 값을 두 번 XOR하면 원래 값으로 돌아온다는 성질을 이용하는 것입니다.
구체적인 진행 과정은 다음과 같습니다.
각 반복 단계에서 먼저 XOR ^ arr[i - k]를 수행하여 마지막 인덱스 + 1부터 현재 인덱스 - 1까지의 부분 배열 값을 얻습니다. 이는 윈도우에서 빠지는 요소를 제거하는 과정입니다.
그런 다음 현재 부분 배열의 XOR 값에 arr[i]를 XOR 연산하여 새로운 윈도우의 XOR 값을 계산합니다. 마지막으로 모든 XOR 값 중 최댓값을 찾아 반환하면 됩니다.
이 방법의 시간 복잡도는 O(n)으로, 단순 반복문 방식보다 훨씬 효율적입니다.
구현 예제 코드
아래는 위 해결 방법을 C++로 구현한 프로그램입니다.
#include<iostream>
using namespace std;
int findMaxSubArrayXOR(int arr[], int n, int k) {
int currentXORVal = 0;
for (int i = 0; i < k; i++)
currentXORVal = currentXORVal ^ arr[i];
int maxXor = currentXORVal;
for (int i = k; i < n; i++) {
currentXORVal = currentXORVal ^ arr[i-k];
currentXORVal = currentXORVal ^ arr[i];
maxXor = max(maxXor, currentXORVal);
}
return maxXor;
}
int main() {
int arr[] = {3, 1, 6, 2, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
cout<<"크기가 "<<k<<"인 부분 배열의 최대 XOR 값은 "<<findMaxSubArrayXOR(arr, n, k);
return 0;
}출력 결과
크기가 3인 부분 배열의 최대 XOR 값은 12
마무리
이처럼 XOR의 대칭 성질(x ^ a ^ x = a)을 활용한 슬라이딩 윈도우 기법을 사용하면, 매번 부분 배열 전체를 다시 계산하지 않고도 이전 결과를 재활용하여 효율적으로 문제를 해결할 수 있습니다. 배열 기반 문제에서 윈도우 이동 기법은 매우 유용하게 활용되는 패턴이므로 꼭 익혀두시길 바랍니다.