문제 소개
이번 튜토리얼에서는 4개의 배열에서 각각 하나씩 원소를 선택해 만든 쿼드러플(quadruple) 중, 그 XOR 연산 결과가 주어진 값 x와 같아지는 조합의 개수를 구하는 프로그램을 다룹니다.
즉, 4개의 배열과 값 x가 입력으로 주어졌을 때, 각 배열에서 원소를 하나씩 골라 만들 수 있는 모든 조합을 검사하여 XOR 값이 x와 정확히 일치하는 경우의 수를 세는 것이 우리의 목표입니다.
접근 방법: 브루트 포스(Brute Force)
가장 직관적인 방법은 4중 반복문을 사용해 가능한 모든 조합을 하나씩 확인하는 것입니다. 각 단계에서 선택된 네 원소의 XOR 값을 계산하고, 그 결과가 x와 같다면 카운트를 1씩 증가시킵니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
// XOR이 x와 같은 쿼드러플 개수 세기
int count_quad(int a[], int b[], int c[], int d[],
int x, int n) {
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
for (int l = 0; l < n; l++)
if ((a[i] ^ b[j] ^ c[k] ^ d[l]) == x)
count++;
return count;
}
int main() {
int x = 3;
int a[] = {0, 1};
int b[] = {2, 0};
int c[] = {0, 1};
int d[] = {0, 1};
int n = sizeof(a) / sizeof(a[0]);
cout << count_quad(a, b, c, d, x, n) << endl;
return 0;
}실행 결과
4
위 예제에서는 각 배열의 크기가 2이므로 총 2×2×2×2 = 16가지 조합이 존재하며, 이 중 XOR 결과가 3이 되는 조합은 4개입니다.
시간 복잡도 분석
브루트 포스 방식의 시간 복잡도는 O(n⁴)입니다. 배열의 크기가 작을 때는 문제없지만, n이 커지면 실행 시간이 급격히 늘어나므로 비효율적일 수 있습니다.
최적화: 미트 인 더 미들(Meet in the Middle)
배열을 두 그룹으로 나누면 시간 복잡도를 O(n²)까지 줄일 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- a[i] ^ b[j]의 모든 결과를 해시맵에 저장합니다.
- c[k] ^ d[l] ^ x의 값이 해시맵에 존재하는지 확인합니다. XOR의 성질상 (a[i] ^ b[j]) == (c[k] ^ d[l] ^ x)이면 전체 XOR이 x가 됩니다.
#include<bits/stdc++.h>
using namespace std;
int count_quad_fast(int a[], int b[], int c[], int d[],
int x, int n) {
unordered_map<int, int> ab;
// a[i] ^ b[j]의 모든 결과를 해시맵에 저장
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
ab[a[i] ^ b[j]]++;
int count = 0;
// c[k] ^ d[l]과 짝이 되는 값 찾기
for (int k = 0; k < n; k++)
for (int l = 0; l < n; l++) {
int need = c[k] ^ d[l] ^ x;
auto it = ab.find(need);
if (it != ab.end())
count += it->second;
}
return count;
}이 방식은 추가로 O(n²) 크기의 해시맵 메모리를 사용하지만, 대규모 입력에서 실행 속도를 크게 개선할 수 있다는 장점이 있습니다.
마무리
정리하면, 4개 배열에서 XOR이 x와 같은 쿼드러플의 개수를 구하는 문제는 단순한 4중 반복문으로 해결할 수 있으며, 해시맵을 활용한 미트 인 더 미들 기법으로 O(n⁴)에서 O(n²)까지 최적화할 수 있습니다. 실무나 코딩 테스트에서는 입력 크기에 따라 적절한 방식을 선택하는 것이 좋습니다.