[알고리즘][python] 부분집합 만들기 : 비트 연산

배열이 주어졌을 때 그 배열의 부분집합을 만드는 방법에는 여러가지 방법이 있지만 세 가지 정도를 생각해볼 수 있을 것 같다.

1. 비트 연산을 이용하는 방법
2. 단순 반복문과 배열을 이용하는 방법
3. 재귀호출을 이용하는 방법

오늘은 1, 2 번 방법을 이용해서 부분집합을 구하는 방법을 살펴보려고 한다.

비트 연산을 이용하는 방법

파이썬의 시프트 연산자

• << : 비트를 좌측으로 옮긴다. 예를 들어 숫자 3을 이진수로 표현하면 11이다. 만약 3 << 1 이라면 전체 비트를 좌측으로 한 칸 옮기고 거기에 0을 채워서 110이 되고 이를 10진수로 표현하면 6이 된다. 즉, 비트를 좌측으로 한 번 옮긴다는 것은 *2를 하는 것과 마찬가지가 된다.
• >> : 비트를 우측으로 옮긴다. 예를 들어 숫자 4를 이진수로 표현하면 100이다. 만약 4 >> 1이라면 전체 비트를 우측으로 한 칸 옮겨서 10이 되고 이를 10진수로 표현하면 2가 된다. 다시 말해서 비트를 우측으로 한 번 옮긴다는 것은 /2를 하는 것 과 같다.

부분집합의 개수

학창 시절에 집합을 배우면 부분집합의 개수에 대해서 꼭 배웠었다. 집합의 원소의 개수가 N이라면 부분집합의 개수는 2^N개였다. 이를 비트 연산으로 표현하면 1 << N이다.

왜 2^N개인지 생각해보면, 각각의 원소는 독립적이어서 원소 각각은 부분집합에 포함되거나/포함되지 않거나 두 가지 경우의 수를 가진다. 만약 원소가 1,2,3으로 이루어진 집합의 부분집합을 구한다면, 각 원소가 두 가지 경우의 수를 가지므로 2 * 2 * 2개의 경우의 수가 생길 것이다. 그래서 2^N개의 부분집합을 만들 수 있는 것이다.

이를 비트로 표현한다면 해당 원소가 포함된다면 1, 포함되지 않는다면 0으로 표현할 수 있다. 다시 말해 001이라면 {3}, 010이라면 {2}, 011이라면 {2,3}으로 표현할 수 있는 것이다. 이 원리를 이용해서 부분집합을 구할 수 있다.

python 코드로 부분집합을 구해보기

arr = [1,2,3] 
for i in range(1<<3): # 공집합을 제외한 모든 부분집합 검사 
    for j in range(3): # arr의 모든 원소 루프
        if i & (1<<j): # i의 j번째 비트 검사, j번째 비트가 1이라면 arr[j] 출력
            print(arr[j], end=' ') # 출력하면 순서가 바뀜에 유의, 다시 말해서 0번째 비트를 검사하면 3의 위치를 검사하는데 arr[j]는 arr[0]을 말한다. 고로 1이 출력됨.
    print()

단순 반복문과 배열을 이용하는 방법

# 부분 집합 만들기 
C = 3
arr = [i for i in range(C)]

subset = [[]] # size = 1

for num in arr:
    size  = len(subset)
    for y in range(size):
        subset.append(subset[y] + [num])

print(subset) # [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]]