파이썬으로 주어진 숫자의 그레이 코드 변환하기

그레이 코드(Gray Code)는 이진수를 배열하는 특별한 방식으로, 연속된 두 숫자의 값이 정확히 한 비트만 차이 나도록 순서를 정하는 방법입니다. 그레이 코드의 예시는 [0, 1, 11, 10, 110, 111, ...]와 같습니다.

숫자 n이 주어졌을 때, 해당 숫자에 대한 그레이 코드(n번째 그레이 코드)를 구해야 한다고 가정해 봅시다.

예를 들어 입력이 n = 12라고 하면, 결과는 10이 됩니다. 12는 이진수로 (1100)이며, 여기에 대응하는 그레이 코드는 (1010)이고, 이 값의 십진수 표현은 10입니다.

문제 해결 접근 방법

이 문제는 재귀적으로 해결할 수 있습니다. 핵심 아이디어는 n보다 크지 않은 가장 큰 2의 거듭제곱(x)을 찾은 뒤, 나머지 부분을 미러링(mirroring)하여 처리하는 것입니다. 다음 단계를 따릅니다:

• solve() 함수를 정의하고, 이 함수는 숫자 n을 인자로 받습니다.
• n이 0이면 0을 반환합니다.
• x를 1로 초기화합니다.
• x * 2 <= n을 만족하는 동안 x를 계속 2배씩 늘립니다. (n 이하의 최대 2의 거듭제곱을 찾는 과정)
• x + solve(2 * x - n - 1)을 반환합니다.

구현 예시

class Solution:
    def solve(self, n):
        if n == 0:
            return 0
        x = 1
        while x * 2 <= n:
            x *= 2
        return x + self.solve(2 * x - n - 1)

ob = Solution()
n = 12
print(ob.solve(n))

입력

12

출력

10

더 간단한 방법: XOR 비트 연산 활용

참고로, 그레이 코드는 비트 연산을 사용하면 한 줄로도 구할 수 있습니다. n과 n을 오른쪽으로 1비트 시프트한 값을 XOR하면 됩니다:

def solve(n):
    return n ^ (n >> 1)

n = 12
print(solve(n))  # 출력: 10

이 방법의 원리는 다음과 같습니다. 12(1100)를 오른쪽으로 1비트 시프트하면 6(0110)이 되고, 1100 XOR 0110 = 1010, 즉 십진수 10이 됩니다. 재귀 방식보다 시간 복잡도 면에서 훨씬 효율적이므로 실무에서는 이 방법을 권장합니다.