C++에서 최소 XOR 값을 가지는 쌍 찾기

문제 개요

정수로 이루어진 배열이 주어졌을 때, 배열 내 서로 다른 두 원소를 선택하여 만들 수 있는 XOR 값 중 가장 작은 값을 갖는 쌍을 찾는 문제입니다.

예시

배열 arr[] = {10, 20, 30, 40}이 주어진 경우, 각 쌍의 XOR 값을 계산해 보면 다음과 같습니다.

(10 ^ 20) = 30
(10 ^ 30) = 20
(10 ^ 40) = 34
(20 ^ 30) = 10
(20 ^ 40) = 60
(30 ^ 40) = 54

위 결과에서 알 수 있듯이, 최소 XOR 값은 10이며 이는 20과 30의 쌍에서 나옵니다.

알고리즘 접근 방식

가장 직관적인 해결 방법은 브루트 포스(완전 탐색) 기법입니다.

• 주어진 배열에서 만들 수 있는 모든 쌍 (i, j)을 생성합니다.
• 각 쌍에 대해 XOR 값을 계산합니다.
• 계산된 값들 중 최솟값을 반환합니다.

이 방법의 시간 복잡도는 두 개의 중첩 반복문을 사용하므로 O(n²)이며, 공간 복잡도는 추가 메모리가 필요하지 않아 O(1)입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int getMinValue(int *arr, int n) {
    int minValue = INT_MAX;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            minValue = min(minValue, arr[i] ^ arr[j]);
        }
    }
    return minValue;
}

int main() {
    int arr[] = {10, 20, 30, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum value = " << getMinValue(arr, n) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Minimum value = 10

마무리

이처럼 완전 탐색 방식은 구현이 간단하고 직관적이지만, 입력 크기가 커질수록 성능이 저하됩니다. 실제 대용량 데이터에서는 배열을 정렬한 후 인접한 원소들의 XOR 값만 비교하는 O(n log n) 최적화 기법을 활용할 수 있습니다.