비트마스킹을 활용하여 원소의 개수 n이 주어질 때
모든 조합의 경우의 수를 구할 수 있다.
n = 4
for i in range(1<<n):
nums = []
for j in range(n):
if i&(1<<j):
nums.append(j)
print(*nums)
결과는 다음과 같다.
0
1
0 1
2
0 2
1 2
0 1 2
3
0 3
1 3
0 1 3
2 3
0 2 3
1 2 3
0 1 2 3
무슨 원리일까?
1. << 연산
for i in range(1<<n):
우선 처음 반복문에 나오는 이것. << 연산은 비트 연산으로, 비트를 왼쪽으로 한칸씩 밀어내는 연산자이다.
1은 2진법으로 00001로 표현되는데
만약 1<<1이면 비트를 한칸씩 밀어내서 00010이 되고(십진법으론 2)
1<<2이면 같은 방식으로 00100이 되고(십진법으론 4)
여기서 n이 4이므로 10000이 된다.(십진법으론 16)
근데 이때 1<<4는 16인데 16은 원소 4개로 만들수있는 조합의 경우의 수와 같다.
여기서 비트마스킹을 사용하는 이유가 드러난다.
비트를 통해 존재하는 원소를 1, 존재하지 않는 원소를 0 으로 대응시키면
1<<n 가지의 케이스에 모든 경우의 수를 대응시킬 수 있다.
다시 말하면 0000~1111에 각 숫자 0~15을 대응시킬 수 있다.
2. 비트 연산 스킬
if i&(1<<j):
여기서 i&(1<<j)가 의미하는 바는
i라는 숫자의 비트에서, 오른쪽으로부터 j번째 자리가 1인가? 라는 뜻이다.
예를 들어 i = 7이라고 해보자. 비트로는 0111가 될 것이다.
j는 2라고 해보자. 1<<j는 그럼 1<<2이므로 0100이 된다.
이제 비트 연산 중 &연산을 해보자. &는 And 연산으로, 둘 다 1이면 1, 나머지 경우는 0으로 계산하는 연산이다.
0111&0100을 그럼 해보면 0100이된다.
잘 생각해보면 (1<<j)는 어차피 1이 j번째에만 존재한다. 이 자리에 1이 있으면 i&(1<<j)결과는 무조건 1이 나올테고
이 자리가 0이면 i&(1<<j) 결과는 무조건 0이 나온다. 즉 이 자리에 1이 있냐 없냐하는 결과를 리턴하는 것이다.
댓글