[알고리즘] 비트연산자를 활용하여 부분집합 만들기

비트연산자를 활용하여 부분집합 만들기

n이 어떤 집합의 원소 갯수라고 하자.

- 특정 부분집합에 대한 특정 원소의 포함여부는 각 원소마다 2가지 경우를 가진다. (들어간다 or 들어가지 않는다.)
- 이를 원소의 갯수만큼 반복하여 생각하면, 모든 부분집합의 경우의 수를 알 수 있다.
- 즉, 어떤 집합의 부분집합은 2의 n승 만큼 존재한다고 할 수 있다.

---

이를 활용하여 특정 집합의 부분집합들을 찾을 수 있다.

- 우선 부분집합의 개수를 비트 형태로 생각해보자. 배열 arr이 6개의 원소를 가진다면,
- 000000~111111의 숫자로 대변할 수 있는 부분집합들을 가질 것이다. (2의 n승개)

---

이를 기반으로 각 부분집합을 한줄씩 출력해주는 코드를 작성해보았다.

 

arr = [3,6,7,1,5,4]
n = len(arr)
 
for i in range(1<<n): 
    for j in range(n): 
        if i & (1<<j):
            print(arr[j], end='')
    print()
 

 

이를 분석해보자.

---

for i in range(1<<n):

 

- 000000 ~ 111111의 경우를 모두 확인해야 한다. 이를 코드로 표현하여 for문으로 반복시킨다.

 

for j in range(n):

 

- 원소는 n개(6개)만큼 존재하므로, 각 인덱스마다 해당 원소가 이번 부분집합에 들어갈지 말지를 확인한다.

- 이를 반복문으로 모두 확인한다.

 

if i & (1<<j):

 

- 핵심이 되는 확인 조건문이다.
- 처음 반복문을 돌렸던 000000~111111의 수가 활용된다.
- 1이 j번 왼쪽으로 시프트되면서 1~100000 따위의 형태를 띄고, i값인 000000~111111의 숫자와 비교된다.
- 이 연산이 if문을 통과하려면 i값의 오른쪽부터 n번째 비트값이 1이어야만 한다. (1<<j는 최상위 자리를 제외하고는 모두 0이기 때문이다.)
- 따라서 해당 자리에 넣을지 말지에 대한 경우의 연산이 처리된다.

 

print(arr[j], end='')

 

- 확인 조건문을 통과하면, 해당 원소를 출력한다. 다음 원소 출력에 대비하여 끝머리 구문은 ''로 처리한다.

print()

 

- 하나의 부분집합에 대한 확인이 끝날때마다 줄을 바꿔준다.

---

이상이다.

 

비트를 활용하여 부분집합을 만드는 것은 처음 이해하기는 어렵지만 제대로 알아둔다면

if문을 반복하여 부분집합을 만드는 것보다 더 깔끔하게 코드를 짤 수 있을 것으로 예상된다.