양의 정수로 이루어진 배열 arr[]과 값 match가 주어졌을 때, 원소들의 XOR 값이 match와 일치하는 부분집합의 개수를 구하는 것이 목표입니다.
예제
입력
arr[] = {4, 2, 8, 10}, match = 12
출력
XOR 값이 12인 부분집합의 개수: 2
설명
원소들의 XOR이 12가 되는 부분집합은 다음과 같습니다. [4, 8], [4, 2, 10]
입력
arr[] = {3, 5, 2, 7}, match = 5
출력
XOR 값이 5인 부분집합의 개수: 2
설명
원소들의 XOR이 5가 되는 부분집합은 다음과 같습니다. [5], [2, 7]
풀이 접근 방법
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 2차원 배열 arr_2[][]를 사용하며, arr_2[i][j]에는 배열 arr[0..i-1]의 부분집합들 중 원소들의 XOR 값이 j가 되는 경우의 수가 저장됩니다.
먼저 빈 집합에서 XOR 값이 0이 되는 경우는 빈 집합 하나뿐이므로 arr_2[0][0] = 1로 초기화합니다. 이후 점화식은 다음과 같습니다.
arr_2[i][j] = arr_2[i-1][j] + arr_2[i-1][j ^ arr[i-1]]
배열 arr[0..i-2]의 어떤 부분집합의 XOR이 j라면, 새 원소 arr[i-1]을 포함하지 않아도 여전히 XOR은 j입니다. 반대로 arr[0..i-2]의 부분집합의 XOR이 j ^ arr[i-1]이라면, 여기에 arr[i-1]을 추가하면 j ^ arr[i-1] ^ arr[i-1] = j가 되므로 역시 XOR이 j가 됩니다. 최종 결과는 arr_2[size][match]에서 확인할 수 있습니다.
알고리즘 단계
- 정수 배열
arr[]과 정수 변수match를 준비합니다. - 함수
subset_XOR(int arr[], int size, int match)는 입력 배열과 그 길이를 받아 특정 XOR 값을 갖는 부분집합의 개수를 반환합니다. - 처음에
highest = arr[0]으로 초기화한 뒤, for 루프로 배열 전체를 순회하며 최댓값을 찾습니다. temp = (1 << (int)(log2(highest) + 1)) - 1을 계산해 가능한 최대 XOR 값을 구합니다.- XOR 값을 저장할 2차원 배열
arr_2[size+1][temp+1]을 선언하고, 모든 요소를 0으로 초기화합니다. arr_2[0][0] = 1로 설정합니다.- i = 1부터 size까지, j = 0부터 temp까지 반복하며
temp_2 = arr_2[i-1][j ^ arr[i-1]]를 구하고arr_2[i][j] = arr_2[i-1][j] + temp_2로 갱신합니다. - 모든 반복이 끝나면
arr_2[size][match]에 특정 XOR 값을 갖는 부분집합의 개수가 저장됩니다. arr_2[size][match]를 결과로 반환합니다.
C++ 예제 코드
#include<bits/stdc++.h>
using namespace std;
int subset_XOR(int arr[], int size, int match){
int highest = arr[0];
for (int i = 1; i < size; i++){
if(arr[i] > highest){
highest = arr[i];
}
}
int temp = (1 << (int)(log2(highest) + 1) ) - 1;
if( match > temp){
return 0;
}
int arr_2[size+1][temp+1];
for (int i = 0; i<= size; i++){
for (int j = 0; j<= temp; j++){
arr_2[i][j] = 0;
}
}
arr_2[0][0] = 1;
for (int i=1; i<=size; i++){
for (int j=0; j<=temp; j++){
int temp_2 = arr_2[i-1][j ^ arr[i-1]];
arr_2[i][j] = arr_2[i-1][j] + temp_2;
}
}
return arr_2[size][match];
}
int main(){
int arr[] = {4, 2, 8, 10, 3, 4, 4};
int match = 2;
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of number of subsets having a particular XOR value are: "<<subset_XOR(arr, size, match);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of number of subsets having a particular XOR value are - 8