역추적(백트래킹) 알고리즘으로 n비트 그레이 코드 생성하기

개요

이 글에서는 역추적(Backtracking) 기법을 활용하여 n비트 그레이 코드(Gray Code)를 생성하는 방법을 살펴봅니다.

n비트 그레이 코드는 0부터 2ⁿ − 1까지의 비트 패턴으로, 인접한 두 패턴 사이에 단 하나의 비트만 차이가 나는 것이 특징입니다. 예를 들어 n = 2인 경우 그레이 코드는 (00, 01, 11, 10)이며, 이를 십진수로 변환하면 (0, 1, 3, 2)가 됩니다. 아래에서 구현할 프로그램은 각 그레이 코드에 해당하는 십진수 값을 출력합니다.

알고리즘

generateGray(arr, n, num)

재귀 호출을 통해 비트를 하나씩 처리하며, 각 단계에서 현재 비트 위치(n−1)에 해당하는 값을 XOR 연산으로 뒤집어 두 가지 분기를 탐색합니다.

begin
    if n = 0, then
        insert num into arr
        return
    end if
    generateGray(arr, n-1, num)
    num := num XOR (1 bit left shift of n-1)
    generateGray(arr, n-1, num)
end

동작 원리:

• n이 0이 되면 지금까지 만들어진 num 값을 결과 배열 arr에 추가하고 종료합니다.
• 먼저 현재 비트를 변경하지 않은 상태로 재귀 호출을 수행합니다.
• 이후 num을 (n−1)번째 비트와 XOR하여 해당 비트를 반전시킨 뒤, 다시 재귀 호출을 수행합니다.
• 이 과정을 통해 모든 그레이 코드 조합이 순서대로 생성됩니다.

C++ 구현 예제

#include<iostream>
#include<vector>
using namespace std;

void generateGray(vector<int>&arr, int n, int &num){
    if(n==0){
        arr.push_back(num);
        return;
    }
    generateGray(arr, n-1, num);
    num = num ^ (1 << (n-1));
    generateGray(arr, n-1, num);
}

vector<int> gray(int n){
    vector<int> arr;
    int num = 0;
    generateGray(arr, n, num);
    return arr;
}

main() {
    int n;
    cout << "Enter number of bits: ";
    cin >> n;
    vector<int> grayCode = gray(n);
    for(int i = 0; i<grayCode.size(); i++){
        cout << grayCode[i] << endl;
    }
}

실행 결과

비트 수로 3을 입력했을 때의 출력 결과입니다. 총 2³ = 8개의 그레이 코드가 생성되며, 인접한 값들이 정확히 한 비트씩만 다른 것을 확인할 수 있습니다.

Enter number of bits: 3
0
1
3
2
6
7
5
4

정리

역추적 기법을 사용하면 재귀적으로 비트를 반전시키면서 모든 그레이 코드를 체계적으로 생성할 수 있습니다. 시간 복잡도는 O(2ⁿ)으로, 그레이 코드의 개수 자체가 2ⁿ개이므로 이는 최적의 성능이라 할 수 있습니다.