[알고리즘 공부] #4 비트마스크(BitMask) 알고리즘 with Python

비트마스크(BitMask)

어떤 알고리즘일까?

비트마스크 알고리즘은 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 알고리즘을 말한다. 주로 효율적인 집합 연산을 수행하거나 상태를 관리할 때 사용된다.

 

장점과 단점

• 장점
  비트마스크 연산은 bit 연산이기 때문에 시간복잡도가 O(1)인 경우가 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 작동한다.
  다양한 집합 연산들을 비트연산자로 한 줄로 작성할 수 있기 때문에 코드가 간결해진다.
  더 적은 메모리로 훨씬 많은 경우의 수를 표현할 수 있어서 메모리 관리에 좋다. 
• 단점
  이진수로 된 비트 연산을 이해하고 읽는 것이 직관적이지 않아 가독성이 떨어질 수 있다.
  비트마스크를 사용한 코드의 디버깅이 어렵다.
  비트 연산을 수행할 때 작은 실수로 인해 큰 오류가 발생할 수 있다.
  비트마스크를 사용하여 복잡한 조건이나 상태를 표현하려면 복잡한 비트 연산식을 작성해야 하는데 이는 코드를 복잡하게 만들고 이해하기 어렵게 할 수 있다.

 

언제 사용하는가?

• 부분 집합 생성 및 탐색
  주어진 집합의 모든 부분 집합을 생성하고 탐색하는 데 비트마스크를 사용할 수 있다.
  
• 조합 문제
  특정 조건을 만족하는 요소들의 집합을 찾는 문제에서 비트마스크를 사용하면 효율적으로 해결할 수 있다.
• 상태 압축
  여러 상태를 하나의 정수로 압축하여 관리할 수 있다. 예를 들어 그래프에서 방문 여부를 관리하거나 게임 상태를 관리할 때 비트마스크를 사용할 수 있다.

 

알고리즘 사용 예제

집합의 부분 집합의 합

주어진 정수 배열에서 원소의 합이 특정 값이 되는 부분 집합을 찾는 문제다.

입력

• 정수 배열 nums (최대 길이 20)
• 정수 target

출력

• 원소의 합이 target이 되는 부분 집합의 개수
• 알고리즘 사용
  함수 안에서 다시 자기 자신을 호출하는 부분이 재귀함수 알고리즘이 사용된 부분이다.

입력:
nums = [1, 2, 3, 4, 5]
target = 6

출력:
3
(가능한 부분 집합: [1, 2, 3], [1, 5], [2, 4])

비트마스크를 이용한 해결 방법

이 문제를 해결하기 위해 비트마스크를 사용하여 모든 부분 집합을 생성하고, 각 부분 집합의 합을 계산하여 target과 비교하는 방식으로 접근할 수 있다.

알고리즘

1. nums의 길이를 n이라고 할 때, 0부터 2n−1까지의 모든 비트마스크를 탐색한다.
2. 각 비트마스크에 대해 해당 비트마스크가 나타내는 부분 집합을 구한다.
3. 해당 부분 집합의 합이 target과 같은지 확인한다.
4. 조건을 만족하는 부분 집합의 개수를 센다.

def count_subsets_with_sum(nums, target):
    n = len(nums)
    count = 0
 
    # 모든 부분 집합을 나타내는 비트마스크를 탐색
    for mask in range(1 << n):  # 0부터 2^n - 1까지
        subset_sum = 0
        
        # 각 비트가 켜져 있는지 확인
        for i in range(n):
            if mask & (1 << i):  # i번째 비트가 켜져 있는 경우
                subset_sum += nums[i]
        
        # 부분 집합의 합이 target과 같은지 확인
        if subset_sum == target:
            count += 1
 
    return count
 
# 예제 입력
nums = [1, 2, 3, 4, 5]
target = 6
 
# 함수 호출 및 출력
print(count_subsets_with_sum(nums, target))  # 출력: 3

이 코드는 주어진 배열 nums의 모든 부분 집합을 생성하고, 각 부분 집합의 합이 target과 같은지 확인한다. 이를 위해 비트마스크를 사용하여 각 부분 집합을 표현하고, 효율적으로 탐색한다.

---