코딩테스트 문제 (27) - 리스트에서 부분집합 출력하기

입력으로 숫자가 담긴 리스트가 주어졌을 때 리스트의 모든 부분집합을 출력하는 문제입니다. 지난 포스트에서는 깊이우선탐색으로 (DFS) 풀었지만 간단한 비트 연산자로 해결할 수 있습니다. 비트 연산자란 정수를 2진수로 표현하여 각 비트끼리 연산하는 operator 를 말하는데요, 파이썬에서의 비트 연산자는 비트를 $n$ 칸 만큼 왼쪽으로 옮기는 "<< n"와 $n$ 칸 만큼 오른쪾으로 옮기는 ">> n" 의 두 가지가 존재합니다. 예를 들어 "1<<3" 이라면 1을 왼쪽으로 3칸 옮겨 'b1000==8' 이 되는 것이죠.

예를 들어 [1,2,3] 이란 리스트가 주어졌을 때의 부분집합은 전체 리스트의 인덱스가 0, 1의 조합에 따라 Figure 1과 같이 표현할 수 있습니다. 전체 부분집합의 개수는 리스트 길이가 $l$ 일때, 공집합을 포함하여 $2^l$ 개 만큼 존재하고 1부터 $2^l$ 까지의 숫자를 2진수로 표현하여 각 인덱스 비트와의 AND (&) operation 이 1이 되는 인덱스를 뽑아내면 전체 부분집합을 구할 수 있습니다.

https://itzjamie96.github.io/2020/10/15/python-bitwise-powersets/

예를 들어 6번째 부분집합을 뽑아내고 싶을 때에는 '6==b110' 이므로 "1<<1 == b010', "1<<2 == b100' 과의 AND operation 이 0이 아니므로 배열의 1, 2번째 인덱스 값을 뽑아낸 것이 해당 순서의 부분집합이 됩니다. 또한, 3번째 부분집합을 뽑아내고 싶을 때에는 '3==b011' 이므로 "1<<0 == b001", "1<<1 == b010' 과의 AND operation 이 0이 아니므로 배열의 0, 1번째 인덱스 값을 뽑아낸 것이 해당 순서의 부분집합이 됩니다. 이를 코드로 나타내면 다음과 같습니다.

def solution(arr):
    n = len(arr)

    for i in range(1 << n):
        for j in range(n):
            if i & (1 << j):
                print(arr[j], end=' ')
        ## 공집합
        print()

 

참조

• https://itzjamie96.github.io/2020/10/15/python-bitwise-powersets/