[Algorithm] 비트 마스크

 

알고리즘 기법이라고 볼 수는 없지만 비트마스크 기법을 이용하여 풀 수 있는 문제가 꽤 보여서 알아보기로 하였다.

 

개념

• 컴퓨터의 최소 연산 단위 bit
• 이진수를 나타내기 위해 0과 1로만 이루어져 있는데, 비트 연산을 통하여 빠르게 해결 할 수 있다.
• 예를 들면 -> bfs나 dfs를 하며 visited를 체크 해줄 때, 크기가 10인 배열을 만드는 경우가 있는데
  • 0b0000000000 와 같이 비트마스킹으로 똑같은 표현을 할 수 있다.
  • 즉 더 작은 메모리를 사용하여 표현 가능하다.

 

장점

• 비트 연산은 삽입, 삭제, 조회가 빠르다.
• 코드가 간결해지며
• 정수 표현으로 dp문제 해결 가능

 

 

비트 연산

2022.08.10 - [ALGORITHM/알고리즘 알아보기] - 알고리즘 - 부분 집합

알고리즘 - 부분 집합

 

이전 포스팅에서 알아 보았다.

위의 연산자들을 바탕으로 실제 알고리즘 풀이에 적용해보자.

 

 

활용

 

1.  원소 추가

n = 3
print(bin(0b0010 | (1 << n))) # 0b1010

 

    2. 원소 삭제

n = 3
print(bin(0b1010 & ~(1 << n)))  #  0b10

 

    3. 원소 조회

• 리턴값이 0이면 없다는 뜻이다.

n = 3
print(bin(0b1010 & (1 << n)))  #  0b1000

 

    4. 원소 역전 (토글)

n = 3
print(bin(0b1010 ^ (1 << n)))  #  0b10

 

    5. 최소 원소 지우기

a = int('0b100100100', 2)

b = a-1
print(bin(b))
# b = '0b100100011'
# 켜져있는 최하위 bit를 끄고 그 밑의 bit를 전부 켠 것

 

    6. 모든 부분집합 순회하기

a = int('0b1101', 2)
subset = a

while True:
	subset = (subset -1) & a
    
    if subset == 0:
    	break
        
    print(bin(subset))
    # 0b1100 -> 1100
    # 0b1001 -> 1001
    # 0b1000 -> 1000
    # 0b101 -> 0101
    # 0b100 -> 0100
    # 0b1 -> 0001

 

 

비트 마스킹을 알고 활용한다면, 파이썬에서도 충분한 메모리와 시간으로 풀 수 있는 문제가 꽤 많은 것 같다.

 

문제 추천

1. https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

2. https://www.acmicpc.net/problem/1562

1562번: 계단 수