비트 연산의 대표 주자인 XOR(배타적 논리합)은 두 비트가 서로 다를 때 1을, 같을 때 0을 반환하는 연산입니다. 만약 10만 개의 숫자가 들어있는 거대한 배열에서, "임의의 두 숫자를 뽑아 XOR 연산을 했을 때 나올 수 있는 가장 큰(Maximum) 결과값을 구하시오"라는 문제를 만났다면 어떻게 풀어야 할까요? 10만 개 중 2개를 뽑는 조합이므로 이중 for 반복문을 사용하여 모든 경우의 수를 검사하는 O(N^2) 방식을 쓰면 100억 번의 연산이 발생해 무조건 시간 초과(TLE)가 납니다. 이 어마어마한 연산량을 O(N)으로 획기적으로 줄여주는 천재적인 해법이 있습니다. 바로 문자열 검색에 쓰이던 트라이(Trie) 자료구조를 이진수 비트(Bit)에 접목시키는 방법입니다. 비트와 트리의 기막힌 만남을 통해 최대 XOR 값을 도출하는 원리를 파헤쳐 보겠습니다.
1. 왜 하필 트라이(Trie)인가? (비트 쪼개기)
트라이는 원래 "APPLE" 같은 문자열을 'A'-'P'-'P'-'L'-'E' 단위로 쪼개어 계층적으로 저장하는 접두사 트리입니다. 이 개념을 32비트 정수(Integer)에 그대로 가져옵니다. 십진수 13은 이진수로 1101(2)입니다. 이를 문자열처럼 취급하여, 트리의 맨 꼭대기(루트)부터 시작해 비트가 1이면 오른쪽 자식, 0이면 왼쪽 자식으로 내려가며 32층 높이의 깊은 트리를 만들어 숫자를 저장하는 것입니다.
1-1. 최상위 비트(MSB)부터 쑤셔 넣기
숫자의 크기를 결정짓는 가장 중요한 비트는 맨 앞쪽에 있는 최상위 비트(Most Significant Bit, MSB)입니다. 맨 앞자리가 1인 것이 뒤쪽 자리가 1인 것보다 무조건 압도적으로 큽니다. 따라서 숫자를 트라이에 삽입할 때는 항상 31번째 비트(맨 앞)부터 시작하여 0번째 비트(맨 뒤) 순서대로 쪼개어 자식 노드로 뻗어 내려가며 트리 구조를 완성해 둡니다. 배열의 모든 숫자를 이 비트 트라이에 넣는 데 걸리는 시간은 32 * N, 즉 O(N)밖에 걸리지 않습니다.
2. 탐욕적(Greedy) 탐색: 최대 XOR를 향한 반개구리 전법
배열의 모든 숫자가 트라이에 세팅되었다면, 이제 다시 배열을 순회하며 각 숫자마다 "트라이에 들어있는 숫자 중 누구랑 XOR를 해야 내가 가장 커질까?"를 찾아냅니다. XOR는 '두 비트가 서로 다를 때 1'이 되므로, 값이 커지려면 무조건 나와 반대되는 비트를 찾아가야 합니다.
2-1. 트라이 탐색 시뮬레이션
내 숫자가 1101(2)이라고 가정해 봅시다. 트라이의 루트에서 시작하여 아래로 내려갑니다.
- 내 첫 번째 비트는
1입니다. XOR 값을 극대화하려면 상대방의 첫 번째 비트는0이어야 합니다. 트라이의 자식 노드 중0으로 가는 길이 있는지 확인합니다. - 길이 있다면 (나와 반대되는 비트가 존재함): 빙고! 그 반대 길(
0)로 내려갑니다. 이때 내 임시 결과값에(1 << 현재 자릿수)를 더해줍니다. 최고로 큰 자릿수를 1로 켰으므로 엄청난 이득을 본 것입니다. - 길이 없다면 (나와 똑같은 비트밖에 없음): 어쩔 수 없이 나와 같은
1의 길로 내려갑니다. 두 비트가1 XOR 1 = 0이 되므로, 이번 자릿수에서는 점수를 얻지 못하고 그냥 0으로 지나칩니다. - 내 다음 비트는
1입니다. 다시 상대방의0길을 찾습니다... (이를 32번 반복)
3. 극강의 시간 복잡도 최적화 (O(N))
이 논리를 사용하면, 숫자 하나당 트라이를 32층만 타고 내려오면(상수 시간) 해당 숫자와 매칭했을 때의 가장 거대한 XOR 짝꿍 값을 100% 확정 지을 수 있습니다.
전체 데이터 N개를 트라이에 삽입하는 데 O(32 * N), 다시 N개의 데이터마다 트라이를 탐색하며 최대 XOR 값을 갱신하는 데 O(32 * N)이 소요됩니다. 결국 총합 O(64 * N)이라는 선형 시간 복잡도로 귀결됩니다. 10만 개의 데이터라면 이중 for문의 100억 번 연산을 고작 640만 번의 초고속 연산으로 대체해 내는, 자료구조(Trie)와 탐욕법(Greedy), 비트 연산(Bitwise)이 완벽하게 결합된 컴퓨터 공학 알고리즘의 예술 작품입니다.
1. 배열 내 최대 XOR 구하기는 O(N^2)의 브루트 포스 방식을 피하기 위해, 이진수 비트를 문자열처럼 쪼개어 저장하는 트라이(Trie) 자료구조를 활용합니다.
2. 가장 큰 자릿수를 결정짓는 최상위 비트(MSB)부터 트리에 차곡차곡 삽입하여, 탐색 시 가중치가 가장 높은 앞자리부터 대조를 시작할 수 있게 만듭니다.
3. 탐색 시에는 XOR의 특성을 이용해 무조건 '현재 내 비트와 반대되는 비트(0이면 1, 1이면 0)'의 경로가 트리에 존재하는지 우선적으로 찾아가는 탐욕적(Greedy) 방식으로 O(N) 속도를 달성합니다.