비트 연산자와 부분집합

파이썬에서 부분 집합을

구할 수 있는 방법은

여러 가지가 있지만

 

오늘은 그 중에서도

비트 연산자를 사용해

부분 집합을 구하는 방법에 대해서 알아보려 한다.

 

비트 연산과 부분 집합

 

비트 연산자는 쉽게 말해

각 비트의 자리를 2진수로

논리 연산을 진행하여

부분 집합을 구하는 방식이다.

 

예를 들어

arr = ["A", "B", "C"]라는

리스트를 가지고 있다면

세 자리를 가진 비트와의 비교를 통해

해당 자리의 각각의 요소들이

포함되는지를 확인하는 방법이다.

 

각각의 요소들이 포함된다면 1을

포함되지 않는 경우라면 0이라는

값을 가지게 된다.

 

부분 집합의 경우

각 자리의 요소들이 포함되거나 혹은 포함되지 않는

2가지의 경우가 있기에

 

총경우의 수는 2^(리스트 요소 개수, 즉 리스트 길이)가

나올 수 있다.

 

만일 '101'과 같이

첫 번째와 마지막에 1이 들어간다면

A와 C가 포함된 집합을

 

'011'과 같이

두 번째와 마지막이 1이 있다면

B와 C가 포함된 집합을

보여주는 것이다.

(구현에 대한 설명은 부분집합 파트에서 자세히 진행하겠다.)

 

사실 비트 연산자는

처음에 글만 읽고는 이해하기 쉽지 않다고 생각한다.

 

하지만 예시를 통해 보면서

하나하나 손으로 직접 코드를 구현해보면

조금 더 쉽게 이해할 수 있을 것이다.

 

비트 연산자

 

코드를 구현하기 전

비트 연산에 사용되는 연산자에

대해서 먼저 알아보자.

 

1. & (and 연산자)

 

대응하는 두 비트가

모두 1일 경우에만 1을 반환한다.

 

2. | (or 연산자)

 

대응하는 두 비트 중

하나 이상이 1일 경우에 1을 반환한다.

 

3. << (left shift 연산자)

 

비트를 왼쪽으로 이동하는 연산자

이는 후의 코드 구현에서 사용될 것으로 알아두자.

 

* 만일 '1<<3'이라면

1을 왼쪽으로 3번 옮긴 것으로

1000로 변환하여 8이라는 결과 값을 출력하게 된다.

 

4. >> (right shift 연산자)

 

비트를 오른쪽으로 이동하는 연산자.

 

 

비트 연산자로 부분 집합 코드 구현

 

아래와 같이

alpha = ["A", "B", "C"]
N = len(alpha)

알파벳이 들어간 리스트 arr과

그 리스트의 길이가 담긴 N이 있다.

 

이 리스트의 부분 집합을 표현하기 위한

코드는 아래와 같다.

for i in range(1<<N):
    for j in range(N):
        if i & (1<<j):
            print(alpha[j], end=" ")
    print()

우선 모든 집합의 경우의 수를

확인하기 위한 for문과

 

집합 안의 요소들이 포함되는지를

판단하는 for문을 사용해

 

부분집합을 구할 수 있다.

 

코드에 대한 자세한 설명은 아래와 같다.

for i in range(1<<N):
# 앞서 말했듯 부분 집합의 개수는 총 2(들어있거나 or 들어있지 않거나)^N(리스트 요소 개수)
# if i = 0 -> 비트 연산자는 000 : 공집합(모든 자리가 들어있지 않음=0)
# if i = 1 -> 비트 연산자는 001 : 첫 번째 자리 요소가 포함된(=1) 집합
# if i = 2 -> 비트 연산자는 010 : 두 번째 자리 요소가 포함된 집합
# 중간 생략
# if i = 6 -> 비트 연산자는 110 : 첫 번째 자리와 두 번째 자리 요소가 포함된 집합
# if i = 7 -> 비트 연산자는 111 : 모든 자리 요소가 포함된 집합
    for j in range(N):
    # 각각의 자리를 확인하기 위한 j
    # if j = 0 -> 첫 번째 자리 확인
    # if j = 1 -> 두 번째 자리 확인
    # if j = 2 -> 세 번째 자리 확인
        if i & (1<<j):
        # 만일 비교했을 때 값이 1인 자리는
            print(alpha[j], end=" ")
            # 출력한다. 그리고 같은 집합 안의 다음 번 요소를 확인하기 위해 end=" "처리
    print()
    # 만일 j가 for문을 다 돌았으면 다음 집합을 확인할 차례이므로 공백 출력

 

마무리

 

부분 집합을 처음 이해하는데

굉장히 어려움을 겪었다.

 

코드가 짧다 보니 이해하기도 전에

코드를 외워서 사용하고 있었고

 

그러다 보니 시간이 지나고 비트 연산자가 기억이 안 날 때 즈음은

비트 연산자를 사용하지 못하는 스스로를 볼 수 있었다.

 

이번 기회를 통해 이해의 중요성을 다시 한번 인지하며

직접 종이에 코드의 흐름을 따라가 보며

다행히 비트 연산자의 이해를 마무리할 수 있었다.

 

*잘못된 부분이 있다면 댓글 부탁드리겠습니다!