오늘은 비트 연산자를 이용한 부분집합 구하기에 대해서 정리해보도록 하겠다.
우선 완성된 코드는 이렇다.
array = [1, 2, 3]
n = len(array)
for i in range (1<<n):
for j in range(n):
if i & (1<<j):
print(array[j], end=" ")
print()1
2
1 2
3
1 3
2 3
1 2 3
참고로 출력값은 오른 쪽과 같다.
자, 그러면 이제 하나하나씩 뜯어보자.
먼저 부분집합의 개수는 각 원소마다 들어가거나/들어가지 않거나 2가지 경우가 있다.
따라서 원소의 개수가 n 일 때, 만큼의 부분집합이 생긴다. (공집합 포함)
위 예에서는 array의 원소 개수가 3이므로, 총 8개의 부분집합이 생긴다.
1. for i in range (1<<n)
‘<<’ 은 비트 쉬프트 연산자(shift) 이다. 쉽게 말해 1을 왼쪽으로 한칸씩 옮긴다고 생각하면 된다.
여기에서 range(1<<n)은 가지 경우의 수에 대해서, 반복하기 위해서 사용한 범위이고.
i는 0부터 (-1)까지의 수를 2진수로 바꾼 값을 말한다. 즉
i = (0 0 0), (0 0 1), (0 1 0), (0 1 1) ….. (1 1 1) 로 반복문이 돌아간다.
2. for j in range (n)
j는 리스트의 인덱스로써 사용되고,
이 경우에 j는 j = 0, 1, 2 에 대해서 돌아간다.
3. if i & (1<<j) :
이 줄이 핵심이다. 여기서부터는 그림과 말을 통해서 설명해보도록 하겠다.
여기에서 (1<<j)는 j번만큼 1을 왼쪽으로 옮긴 것이라고 이해하면 된다.
예를 들어 j = 0 이면, 1<< j는 001 이고,
j = 1이면, 1<<j = 010 이다.
비트연산자에서 &는 둘 다 1일때만 1이고, 하나라도 0이면 0이다.
그럼 언제 if i & (1<<j) 가 실행이 될까?
파이썬에서는 ‘0’이 False이고, 그 외의 수는 True이기 때문에,
if 문이 True가 될 때, 즉 i&(1<<j)의 값이 1일 때 아래 print문을 실행하게 된다.
예를 들어 5번째 반복문 즉, i = 101인 상황을 가정해보자.
다음 반복문에서 j = 0, j = 1, j = 2 으로 세번 반복문이 돌아가며
이 때 i<<j 값은 각각 001, 010, 100 이다.
i&1<<j 의 값이 1이 되는 경우는 j = 0일때와 j =2 일때다,
이 때 print의 마지막에 ,end = “ “ 가 있기때문에
a[0] 값인 1과 a[2] 값인 3이
1
3
이 아닌 1 3 의 형태로 한줄로 출력된다.
다시 맨 위로 올라가서 코드 실행 결과의 5번째 줄을 보자! 1 3 인 것을 알 수 있다.
이런식으로 8번을 반복해서 부분집합을 출력하는 것이다.
나머지 경우에 대해서는 직접 생각하고, 돌려보자.
Uploaded by N2T