부분집합을 구하는 알고리즘 - bit 연산 활용

특정 원소들로 이루어진 집합이 있다고 할 때, 이 집합의 부분집합을 구하기 위해 bit 연산을 활용할 수 있다.

 

# 비트연산자 기본
& : 비트 단위로 AND 연산을 한다.
| : 비트 단위로 OR 연산을 한다.
<< : 피연산자의 비트 열을 왼쪽으로 이동시킨다.
>> : 피연산자의 비트 열을 오른쪽으로 이동시킨다.

# << 연산자
1<<n : 2**n, 즉 원소가 n개일 경우 모든 부분집합의 수를 의미

# & 연산자
i & (1<<j) : i의 j번째 비트가 1인지 아닌지를 리턴

 

# bit 연산을 활용해 부분집합 구하기

arr = [1, 2, 3] # 기존 집합
result = [] # 부분집합을 담을 새로운 리스트

n = len(arr) # 원소의 개수

for i in range(1<<n): # 부분집합의 개수
    temp = []
    for j in range(n+1): # 원소의 수만큼 비트를 비교
        if i & (1<<j):
            temp.append(arr[j])
    result.append(temp)

print(result)

 

 

# 결과

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]