파이썬 재귀를 활용한 그레이 코드(Gray Code) 생성 방법

그레이 코드(Gray Code)는 인접한 두 코드 값이 오직 한 비트만 다른 특수한 이진수 체계입니다. 이번 글에서는 파이썬의 재귀적 구조와 반복문을 활용하여 원하는 비트 수만큼의 그레이 코드를 생성하는 방법을 살펴보겠습니다.

핵심 아이디어는 다음과 같습니다. 먼저 빈 리스트를 만들고 기본 값인 0과 1을 추가합니다. 이후 여러 개의 for 반복문을 사용해 기존 코드들을 뒤집어 복사하고, 앞부분에는 0을, 뒷부분에는 1을 붙여가며 코드 목록을 점진적으로 확장합니다.

예제 코드

import math as mt

def generate_gray_list(my_val):
    if (my_val <= 0):
        return
    my_list = list()
    my_list.append("0")
    my_list.append("1")
    i = 2
    j = 0
    while(True):
        if i >= 1 << my_val:
            break
        for j in range(i - 1, -1, -1):
            my_list.append(my_list[j])
        for j in range(i):
            my_list[j] = "0" + my_list[j]
        for j in range(i, 2 * i):
            my_list[j] = "1" + my_list[j]
        i = i << 1
    for i in range(len(my_list)):
        print(my_list[i])

my_num = 3
print("입력된 숫자 :")
print(my_num)
print("그레이 코드 생성 함수가 호출됩니다...")
generate_gray_list(my_num)

실행 결과

입력된 숫자 :
3
그레이 코드 생성 함수가 호출됩니다...
000
001
011
010
110
111
101
100

코드 설명

• 먼저 필요한 패키지(math)를 임포트합니다.

• generate_gray_list라는 메서드를 정의하고, 내부에 빈 리스트를 생성합니다.

• 리스트에 기본 값인 "0"과 "1"을 추가합니다.

• 여러 개의 for 반복문을 사용해 기존 코드를 역순으로 복사하며 리스트를 확장합니다.

• 왼쪽 시프트 연산자(<<)를 활용해 현재 코드 개수를 두 배씩 늘리고, 목표 비트 수(1 << my_val, 즉 2의 거듭제곱)에 도달할 때까지 반복합니다.

• 앞쪽 절반의 코드에는 "0"을, 뒤쪽 절반의 코드에는 "1"을 접두사로 붙입니다.

• 메서드 외부에서 매개변수(my_num = 3)를 전달하며 함수를 호출합니다.

• 생성된 모든 그레이 코드가 콘솔에 순서대로 출력됩니다.

마무리

3비트 입력 시 총 8개(2³)의 그레이 코드가 생성되는 것을 확인할 수 있습니다. 이처럼 재귀적 확장 방식을 사용하면 임의의 비트 수에 대해서도 간결하게 그레이 코드를 생성할 수 있으며, 디지털 회로 설계나 오류 최소화가 중요한 데이터 전송 분야에서 유용하게 활용됩니다.