이번에 외판원 순회 문제를 풀고있는데 dp 와 비트마스킹 기법을 더해서 푸는 문제라고 하더라구요..?
근데.. 나 ?
- 비트마스킹이 뭔지 모름.
그래서 비트마스킹이 뭔지부터 공부해봤습니다.
아니 정글쨩 ㅋㅋㅋㅋ 진짜 서운하다 서운해~!!! 이걸 어케알고 푸냐고~~
1. 비트마스킹이란?
정수의 이진수 표현을 자료구조로 사용하는 기법
각 비트가 0 또는 1의 값을 가지므로, 하나의 정수로 여러개의 boolean 값을 표시하는 기법이예요.
예시를 들어볼게요.
우리가 이미 방문한 곳을 표시하기 위해서 VISTIED 배열을 만들어서 사용한 적 있죠?
# boolean 배열 사용
visited = [False] * 4 # [False, False, False, False]
visited[0] = True # [True, False, False, False]
# 비트마스킹 사용
visited = 0b0000 # 0
visited |= (1 << 0) # 0b0001
# 0b 는 파이썬에서 이진수임을 나타내기 위핸 표시예요!
# 0x 가 16표시인 것과 동일합니다!이런식으로 visited 배열을 만드는 대신에
비트 마스킹 방법으로 0000 을 방문표시로 대체할 수 있어요.
만약 0010 이라면 [ Fasle, True, False, False ] 인 것과 똑같아요!
그리고 Set같은 집합을 대체 할수도 있어요.
# Set 사용
s = set()
s.add(0) # {0}
s.add(2) # {0, 2}
s.add(3) # {0, 2, 3}
# 비트마스킹 사용
s = 0b0000
s |= (1 << 0) # 0b0001
s |= (1 << 2) # 0b0101
s |= (1 << 3) # 0b1101set은 중복을 허용하지 않는 집합인데요.
이런식으로 정수값 0,2,3 을 가지는 집합이라면
비트마스킹의 0b1011로 표시할 수 있어요.
2. 비트마스킹을 쓰는 건 어떤 장점이 있을까?
2-1. 메모리 효율성
첫 번째는 메모리 효율성이예요.
우리가 boolean 배열을 만들어야 한다면
[ True , False , False, False, True ] 처럼 메모리 공간을 사용하게 되는데.
비트마스킹을 쓰면 0b1001로 정수 하나로 표현할 수 있어요.
2-2. 연산 속도
비트 연산은 CPU에서 매우 빠른 속도로 처리돼요.
정글러라면 기본 컴퓨터 시스템공부 했으니까 다 알겠죠~?
3. 기본 비트연산
비트마스킹이 뭔지, 어떤 자료구조를 대체해서 간결하게 할 수 있는지 알아봤어요.
그럼 기본적인 비트연산을 알아보고나서 주요사용법도 알아볼게요.
# 1. AND 연산 (&)
# 두 비트가 모두 1일 때만 1
0b1010 & 0b1100 = 0b1000
# 2. OR 연산 (|)
# 두 비트 중 하나라도 1이면 1
0b1010 | 0b1100 = 0b1110
# 3. XOR 연산 (^)
# 두 비트가 서로 다를 때 1
0b1010 ^ 0b1100 = 0b0110
# 4. NOT 연산 (~)
# 비트를 반전
~0b1010 = 0b0101
# 5. 시프트 연산
# 왼쪽 시프트 (<<): 비트를 왼쪽으로 이동
0b0001 << 2 = 0b0100 # 1을 2칸 왼쪽으로 이동
# 오른쪽 시프트 (>>): 비트를 오른쪽으로 이동
0b0100 >> 2 = 0b0001 # 4를 2칸 오른쪽으로 이동비트의 기본적인 연산들이예요.
AND OR XOR NOT SHIFT 연산들은 위 예제를 통해 확인해보세요.
4. 비트마스킹의 주요 사용법
4-1. 특정 순번 비트 켜기 ( Set )
예를 들어 1,2,3,4 번째 중 2번째만 방문 체크를 하고싶다면?
# n번째 비트를 1로 설정
state |= (1 << n)
# 예시
state = 0b0000
state |= (1 << 2) # 0b0100이런식으로 state |= (1 << 2) 를 해주면 돼요.
state 에 |= 을 사용해주는 이유는 만약 ob1001 인데 state = (1 << 2) 를 하게 되면 결과가 ob0100이 되어서 기존 비트가 사라지기 때문이에요.
그래서 OR연산으로 기존 비트를 유지시켜 주는 거예요.
4-2. 특정 순번 비트 끄기 ( Clear )
1,2,3,4 번째 중 2번째만 비트를 0으로 만들고 싶다면?
# n번째 비트를 0으로 설정
state &= ~(1 << n)
# 예시
state = 0b1111
state &= ~(1 << 2) # 0b1011이렇게 해주면 됩니당.
우선 (1 << 2) 로 비트를 0100 으로 만들어주고
~을 사용해서 1011 로 만들어줘요
그리고 & 연산을 통해 둘다 1 인 경우만 1로 만들어줘요!
기존 값이 0이면 어차피 0이 될테구 1이면 1이 될테니까요!
그럼 한 비트만 0으로 만드는 연산이 가능합니다.
4-3. 특정 비트 토글 ( Toggle )
이건 특정 하나의 비트만 반전시키는 거예요.
1이면 -> 0
0이면 -> 1
이렇게요.
# n번째 비트를 반전
state ^= (1 << n)
# 예시
state = 0b1010
state ^= (1 << 1) # 0b1000(1 << 1) 로 ob0010을 생성해줘요!
그리고 XOR연산으로 비트가 서로 다를 때만 1이 되게 만들어줍니다.
비트가 1이면 0이될테구
비트가 0이면 1이될거예요.
우리는 1을 넣어줬으니까요!
4-4. 특정 비트 확인 ( Check )
n번째 비트가 1인지 0인지 확인하고 싶을 때 사용해요.
# n번째 비트가 1인지 확인
if state & (1 << n):
print("n번째 비트가 1입니다")
# 예시
state = 0b1010
if state & (1 << 1): # True
print("1번째 비트가 1입니다")1번째 비트가 1인지 확인하구 싶어요.
그럼 우선 1번째 비트에 1을 넣는 연산을 사용하고 & 연산을 사용해줘요
둘다 1이면 True 이고 하나라도 0이면 False 겠죠?
마무리
참고로 외판원 순회 문제는 DP + 비트마스킹 방식으로 문제를 해결하기 위해
비트마스킹을 visited 배열처럼 활용합니다.
어떻게요?
안알랴줌 ㅋㅋㅋ
