Subset & Bitwise operator (부분집합과 비트 연산)

설명

유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아보시오.

예: [-7, -3, -2, 5, 8]의 경우 [-3, -2, 5]라는 부분집합이 참이 된다.

위와 같은 문제가 존재할 때, 완전검색 기법으로 접근해야 할 것이다.

우선 집합의 모든 부분집합을 생성하고, 각 부분집합의 합을 계산해야 한다.

부분집합의 수

• 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개
• 각 원소를 부분집합에 포함시키거나, 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 동일

{1, 2, 3, 4} 의 경우 2 X 2 X 2 X 2 = 16
총 16개의 부분집합이 존재

각 원소가 부분집합에 포함되었는지를 for loop를 이용하여 생성하는 방법

bit = [0, 0, 0, 0]

# 부분집합의 수는 2^n 개 이다.
for i in range(2):
    bit[0] = i
    for j in range(2):
        bit[1] = j
        for k in range(2):
            bit[2] = k
            for l in range(2):
                bit[3] = l
                print(*bit)
                # 0 0 0 0
                # 0 0 0 1
                # 0 0 1 0
                # ...
                # 1 1 1 1

4가지 원소에 대해 4번의 중첩 for loop가 작성된다. 복잡하고 시간소요가 길어진다.

이를 개선하기 위해 비트 연산자를 활용한다.

비트 연산자

& : 비트 단위로 AND 연산
| : 비트 단위로 OR 연산
<< : 피연산자의 비트 열을 왼쪽으로 이동
>> : 피연산자의 비트 열을 오른쪽으로 이동

 

비트 연산을 사용해 보다 간결하게 부분집합을 생성하는 방법

# 비트 연산을 사용해 부분집합 생성
arr = [3, 6, 7, 1, 5, 4]

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

for i in range(1<<n):    # 1<<n : 부분 집합의 개수
    for j in range(n): # 원소의 수만큼 비트를 비교
        if i & (1<<j):   # i의 j번째 비트가 1이면 j번째 원소 출력
            print(arr[j], end=", ")
    print()
    # 3,
    # 6,
    # 3, 6,
    # ...
    # 3, 6, 7, 1, 5, 4,