[c++] 트라이의 최대 XOR 합(Maximum XOR in a Trie)

12 Dec 2023

트라이(Trie) 자료 구조는 문자열 검색에 사용되는 효율적인 자료 구조입니다. 이번 포스트에서는 트라이를 사용하여 주어진 숫자 배열에서 최대 XOR 합을 찾는 알고리즘에 대해 다루겠습니다.

문제 설명

주어진 숫자 배열에서 두 개의 숫자를 선택하여 XOR 연산을 수행했을 때, 그 결과가 최대가 되는 경우를 찾는 문제입니다.

예를 들어, 다음과 같은 숫자 배열이 주어졌을 때:

[3, 10, 5, 25, 2, 8]

위 배열에서 선택된 두 숫자의 XOR 연산 결과 중에 최대가 되는 경우는 다음과 같습니다:

10 XOR 25 = 27

알고리즘

이 문제를 해결하기 위해 트라이를 사용합니다. 트라이를 구성하는 각 노드는 한 비트(0 또는 1)를 나타내며, 주어진 숫자를 트라이에 삽입하고, XOR 연산을 통해 최대 XOR 합을 구합니다.

코드 예시

아래는 C++로 작성된 트라이를 사용하여 최대 XOR 합을 구하는 예시 코드입니다.

#include <iostream>
#include <vector>

using namespace std;

class TrieNode {
public:
    TrieNode* children[2];

    TrieNode() {
        children[0] = NULL;
        children[1] = NULL;
    }
};

void insert(TrieNode* root, int num) {
    TrieNode* curr = root;
    for (int i = 31; i >= 0; i--) {
        int bit = (num >> i) & 1;
        if (curr->children[bit] == NULL) {
            curr->children[bit] = new TrieNode();
        }
        curr = curr->children[bit];
    }
}

int findMaxXOR(TrieNode* root, vector<int>& nums) {
    int maxXOR = 0;
    for (int num : nums) {
        TrieNode* curr = root;
        int currXOR = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (curr->children[bit ^ 1] != NULL) {
                currXOR += (1 << i);
                curr = curr->children[bit ^ 1];
            } else {
                curr = curr->children[bit];
            }
        }
        maxXOR = max(maxXOR, currXOR);
    }
    return maxXOR;
}

int main() {
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    TrieNode* root = new TrieNode();
    for (int num : nums) {
        insert(root, num);
    }

    cout << "Maximum XOR: " << findMaxXOR(root, nums) << endl;
    return 0;
}

결론

트라이를 사용하여 주어진 숫자 배열에서 최대 XOR 합을 찾는 알고리즘을 구현했습니다. 이 알고리즘을 사용하면 효율적으로 최대 XOR 합을 찾을 수 있습니다.

참고 문헌:

GeeksforGeeks, “Maximum XOR value of a Pair in an Array”, https://www.geeksforgeeks.org/maximum-xor-value-of-a-pair-in-an-array/