알고리즘 유형공부 - 비트마스킹 (BitMasking)

비트마스킹 (Bitmasking)

1. 개요

비트마스킹(Bitmasking)은 정수를 이진수로 표현하여 각 비트를 활용해 데이터를 효율적으로 처리하는 기법.
주로 집합의 상태를 표현하거나 조합 문제를 해결할 때 사용된다.

2. 알고리즘의 원리

비트마스킹은 비트 연산을 통해 데이터를 조작한다.
비트 연산을 이용해 특정 비트의 ON/OFF 상태를 확인하거나 변경할 수 있다.

비트마스킹의 주요 작업은 다음과 같습니다:

1. 비트 켜기 (Set Bit): 특정 비트를 1로 설정한다.
2. 비트 끄기 (Clear Bit): 특정 비트를 0으로 설정한다.
3. 비트 토글 (Toggle Bit): 특정 비트를 반전한다.
4. 비트 확인 (Check Bit): 특정 비트가 1인지 확인한다.

3. 비트마스킹을 사용하는 이유

• 메모리 절약: 각 비트를 상태로 사용하기 때문에 메모리 사용량이 줄어든다.
• 빠른 연산 속도: 비트 연산은 매우 빠르기 때문에 효율적인 알고리즘을 구현할 수 있다.
• 집합 및 조합 문제 해결: 비트로 집합을 표현하고 연산을 수행할 수 있다.

특히, 부분집합 문제, 조합 최적화 문제, 중복 체크 문제에서 자주 사용한다.

4. 비트 연산자

비트 연산자는 비트를 조작하는 데 사용되며, 각 연산자의 기능과 예제를 이해하면 비트마스킹을 효과적으로 사용할 수 있다.

4.1. 주요 비트 연산자

연산자	설명	예제
&	AND 연산 (비트가 모두 1일 때만 1)	5 & 3 → 0101 & 0011 → 0001
`	`	OR 연산 (비트가 하나라도 1이면 1)
^	XOR 연산 (비트가 다를 때만 1)	5 ^ 3 → 0101 ^ 0011 → 0110
~	NOT 연산 (비트 반전)	~5 → ~0101 → 1010
<<	왼쪽 시프트 (비트를 왼쪽으로 이동)	5 << 1 → 0101 → 1010
>>	오른쪽 시프트 (비트를 오른쪽으로 이동)	5 >> 1 → 0101 → 0010

4.2. 비트 연산자 예제 코드

x = 5       # 0101
print(x & 3)  # 0001 (AND 연산)
print(x | 3)  # 0111 (OR 연산)
print(x ^ 3)  # 0110 (XOR 연산)
print(~x)     # -6 (NOT 연산)
print(x << 1) # 1010 (왼쪽 시프트)
print(x >> 1) # 0010 (오른쪽 시프트)

4.3. 비트 연산 응용

1. 마스크 생성: 특정 비트 위치를 켜거나 끌 때 사용한다.

    mask = 1 << 3  # 3번 비트를 켜기 위한 마스크: 1000

2. 비트 필터링: 특정 비트를 확인하거나 추출한다.

    if x & (1 << 2):
        print("2번 비트가 켜져 있습니다.")

3. 비트 반전: 특정 비트를 토글한다.

    x ^= (1 << 1)  # 1번 비트를 반전

5. 비트마스킹을 통한 집합의 표현 및 연산

비트마스킹은 집합을 표현하는 데 매우 유용한다.
각 비트는 집합의 원소를 나타내며, 비트가 1이면 해당 원소가 집합에 포함되었음을 의미한다.

5.1. 집합 표현

예를 들어, 원소가 {0, 1, 2, 3}인 집합을 비트마스크로 표현할 수 있다.

비트마스크	집합 표현	설명
0000	∅ (공집합)	모든 원소가 포함되지 않음
0001	{0}	0번 원소만 포함
0110	{1, 2}	1번과 2번 원소 포함
1111	{0, 1, 2, 3}	모든 원소 포함

5.2. 비트마스킹으로 집합 연산하기

1. 원소 추가: 원소 i를 집합에 추가하려면 S |= (1 << i)를 사용한다.

    S = 0          # 초기 집합 (공집합)
    S |= (1 << 2)  # 2번 원소 추가: 0100
    print(bin(S))  # 출력: 0b100

2. 원소 제거: 원소 i를 제거하려면 S &= ~(1 << i)를 사용한다.

    S = 0b1011     # 초기 집합: {0, 1, 3}
    S &= ~(1 << 1) # 1번 원소 제거: 1011 -> 1001
    print(bin(S))  # 출력: 0b1001

3. 원소 확인: 원소 i가 집합에 포함되었는지 확인하려면 (S & (1 << i)) != 0를 사용한다.

    S = 0b1010
    print((S & (1 << 3)) != 0)  # True (3번 원소 포함)

4. 원소 토글: 원소 i의 상태를 반전하려면 S ^= (1 << i)를 사용한다.

    S = 0b1001     # 초기 집합: {0, 3}
    S ^= (1 << 0)  # 0번 원소 토글: 1001 -> 1000
    print(bin(S))  # 출력: 0b1000

5. 집합 크기 확인: 집합에 포함된 원소의 개수를 확인하려면 bin(S).count("1")를 사용한다.

    S = 0b1101
    print(bin(S).count("1"))  # 출력: 3

6. 모든 부분집합 생성: 원소가 n개인 집합의 모든 부분집합을 생성한한다.

    n = 3
    for i in range(1 << n):
        subset = [j for j in range(n) if i & (1 << j)]
        print(subset)

   출력:

    []
    [0]
    [1]
    [0, 1]
    [2]
    [0, 2]
    [1, 2]
    [0, 1, 2]

   이 방법은 모든 경우를 확인해야하는 알고리즘 풀이에 굉장히 유용하다.