[leet89] GrayCode, 이진수 표기는 비트연산자(bitwise operator)

leetcode 89 gray code

비트연산자(bitwise operators)

출처: https://wikidocs.net/1161

비트연산자는 이진수 표기에서의 연산이다. 'and', 'or', 'xor'은 한번씩 두 숫자간의 관계에서 비롯하는 것이고 '>>'와 '<<'는 하나의 이진수에서 각각 오른쪽, 왼쪽으로 자리수를 밀어주는 역할을 한다. 실제 데이터 활용에서는 사용해본 적이 없는데 코딩테스트 중 이진수 표기와 관련된 내용이 나올 때에는 꼭 한번씩 떠올려보아야 한다. 그래서 포스팅을 남겨둔다.

Question

이진수로 나타냈을 때 하나의 digit만 달라지도록 십진수 숫자들을 이어붙인다. n은 이진수 자리수를 나타내며, n=2라면, 10, 11, 01, 00 등 두 자리의 이진수만으로 나타낼 수 있는 숫자들을 나열하면 된다. 아래 예시를 보면 이해가 쉬울 것.

Solution

Sol_1: Dynamic Programing

dp[n] = dp[n-1] + [val + 2**(n-1) for val in dp[n-1][::-1]]을 점화식으로 사용한다.
n=2일 때 [0,1,3,2]라면 n=3일 때에는 [0,1,3,2] 뒤에 [2,3,1,0]의 각각 원소에 2^2를 더해준 리스트를 붙여주면 된다. [0,1,3,2,6,7,5,4]가 된다.

def sol_1(n:int) -> List[int]:
    dp = dict()
    dp[1] = [0,1]
    dp[2] = [0,1,3,2]

    def get_list(val:int):
        nonlocal dp
        if val in dp: return dp[val]
        ans = get_list(val-1) + [v + (2**(val-1)) for v in get_list(val-1)[::-1]]
        dp[val] = ans
        return ans
    return get_list(n)

Sol_2: bitwise operators

n=3이라면 index가 0부터 7까지 총 8개의 숫자가 차례로 answer list에 붙는다. 이 때 인접한 숫자끼리는 2진수로 나타냈을 때 하나의 digit만 달라야 한다.
n을 이진수로 나타냈을 때 오른쪽으로 한칸씩 밀고, 원래 숫자와 XOR 연산을 하면, n-1을 그렇게 했을 때와 1개의 digit만 다른 수가 된다. (이건 단순하게 기억해두는 게 편할 듯 하다..)

def sol_2(n:int) -> List[int]:
    ans = list()
    idx = 0
    while idx <= 2**n -1:
        ans.append(idx ^ (idx >> 1))
        idx += 1
    return ans

github