[Algorithm] 비트 연산자의 활용

TOC

• 부분집합 합(Subset Sum) 문제
  • Sol
• 비트 연산자
  • 비트 연산자로 부분집합 생성
  • 비트 연산자의 특징

부분집합 합(Subset Sum) 문제

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

예를 들어, [-7, -3, -3, 5, 8]라는 집합이 있을 때, [-3, -2, 5]는 이 집합의 부분집합이면서 (-3)+(-2)+5=0 이므로 이 경우에 답은 참

Sol

완전검색 기법으로 부분집합 합 문제를 풀기 위해서는, 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야 한다. 주어진 집합의 부분집합을 생성하는 방법에 대해서 생각해보자.

A = [1, 2, 3, 4]
bit = [0]*4
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
       for x in range(4):
        print(bit)

비트 연산자

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

<< 연산자

1 << n : 2^n 즉, 원소가 n개일 경우의 모든 부분집합의 수

& 연산자

i&(1 << j) : i의 j번째 비트가 1인지 아닌지를 검사

비트 연산자로 부분집합 생성

arr = [3, 6, 7, 1, 5, 4]
n = len(arr)

for i in range(1<<n):                   # 1 << n : 부분 집합의 개수
    for j in range(n):                  # 원소의 수만큼 비트 비교
        if i & (1<<j):                  # i의 j번 비트가 1인 경우
            print(arr[j], end=", ")     # arr의 j번 원소 출력
        print()
    print()

좀 더 잘 이해가 되도록 i를 부분집합을 의미하는 subset으로 바꿔보겠다.

arr = [3, 6, 7, 1, 5, 4]
n = len(arr)

for subset in range(1<<n):              # 1 << n : 부분 집합의 개수
    for j in range(n):                  # 원소의 수만큼 비트 비교
        if subset & (1<<j):             # subset의 j번 비트가 1인 경우
            print(arr[j], end=", ")     # arr의 j번 원소 출력
        print()
    print()

1 << n은 결국 0 ~ (2^n-1) 만큼의 수를 의미하는데, 이를 2진수로 나타내면 0이 n만큼 있는 수부터 1이 n만큼 있는 수까지의 수이다. 즉, 위의 같은 경우는 arr의 개수인 n이 6이므로 1 << 6은 64이고, 이를 range(64)로 표현하면 0이상 63이하인 수이다. 이를 2진수로 표현하면 000000부터 111111이다.

이를 다시 해석하면 각 자리의 0 또는 1은 부분집합에 들어가는 원소가 된다. 즉, 111111은 arr 그 자신이 되고, 000000은 아무 원소도 없는 공집합이다.

range(1<<n)를 이용하여 이 수들 전체를 조회할 때 각각의 수를 subset라고 생각한다. ??????의 2진수가 될 것이다. 그리고 원소의 수인 n만큼 자릿수를 j로 계산하는 것이다. 그래서 j는 2진수의 자릿수만을 의미한다.

1<<j이라는 것은 결국 j번째 비트에만 1을 집어넣는 과정이고, 이것을 & subset 처리하면 subset인 ??????의 j번째 비트에 1이 있는지 없는지의 여부에 따라 print(arr[j], end=", ") 코드를 실행하는 것이다. arr[j]는 리스트의 j번째 원소이고, 이를 출력하는 것이다.

이 2중 for문의 궁극적인 의의는 ??????인 subset의 모든 자릿수가 곧 arr 배열의 인덱스가 되고, 각각의 ?마다 0인지 1인지 조회하는데 1이라면 해당 비트의 자릿수에 해당하는 인덱스의 arr 원소가 부분집합의 원소가 된다는 말이다.

비트 연산자의 특징

• 다른 연산자들에 비해 실행 사이클이 짧다.
• 알고리즘 문제 해결에 종종 활용한다.