[Week04] 알고리즘 - 비트 마스킹

백준 외판원 순회 문제(TSP)를 풀려면 비트 마스킹에 관한 개념이 필요하여 공부하게되었다. 

 

해당 문제 

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

2098번: 외판원 순회

 

keywords

비트마스킹 dp, 비트마스킹 bfs, 비트마스크 순열, 비트마스크 조합

 

 

비트 마스킹

컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다.
이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법이다. 

 

check = [False] * 10 와 같이 리스트를 통해 방문 체크를 하는 대신 bit를 이용해서 다양한 알고리즘 문제를 간결한 코드와 빠른 속도로 확인 가능하다. 

 

✅ 작은 메모리와 빠른 수행시간으로 해결이 가능 (그러나 원소의 수가 많지 않아야 함)

✅ 집합을 배열의 인덱스로 표현 가능

✅ 간결한 코드

✅ DP나 순열, 배열 활용만으로 해결할 수 없는 문제

 

 각 정점에 도달했을때 정점에 접근해야하는 값이 1개가 아닐 경우 각 데이터에 대한 접근 여부를 확인하기 위해선 점점 많은 차원의 배열이 필요하다. 각 정점에 저장되는 데이터가 26개 일때, 방문 여부를 포함해서 27차원 배열을 선언해야할까??❗️❗️

 

단순히 방문체크를 위해(0,1이 전부인) 많은 차원의 배열을 사용하는 것은 비효율적여 보인다. 그런 측면에서 비트마스킹이 효율적인 스킬이라는 것을 알수있다. 종종 비트연산을 활용한 숏코드를 보면 멋있어 보였는데 비트마스킹 기법도 잘 알아두면 효율적으로 사용할 수 있을것같다.

 

 

비트연산자

비트 연산자는 많이들 알고있으니 생략한다. 

• and( & ) or( | ) xor( ^ )
• not( ~ )

shift 연산자

•  >> : 2진수 자리수가 하나 증가하므로 값은 *2가 된다. 
• <<  : 2진수 자리수가 하나 감소하므로 값은 /2가 된다. 

비트마스크

방문 배열에서 어떤 연산을 했는지 안했는지 정수 형태로 저장하고, 그걸 이진수로 치환해서 각 자리수마다 어떤 연산의 인덱스를 할당하여 위의 문제를 해결한다.

• 2진수 각 자리마다 작업의 수행여부를 0과 1로 할당

비트마스킹 하기

원소 추가

s |= ( 1 << num )

s 에 num을 추가한다. 즉, num번째 비트만 1을 만들어주면 된다. 

(1 << num) 은 num을 1로 세팅해 주는 동작이며, or연산을 이용해 s와 합쳐준다. 

 

 

원소 삭제

s &= !( 1 << num )

! ( 1 << num )은 num번째 비트만 0으로 만들고 나머지는 1로 만들어주기 위한 동작이다. 

and 연산을 통해 나머지 비트는 동일한 상태를 유지할 수 있다. 

 

 

원소 토글

s ^= ( 1 << num )

s에 num이 없다면 추가, 있다면 삭제 연산

 

 

원소 체크

print( 1 if s & (1 << int(op[1])) != else 0 ))

s에 num이 있으면 1, 없으면 0을 출력해주는 연산이다. and 연산은 두 비트가 모두 1이여야 1을 반환한다는 성질을 이용한다. 

 

 

원소 비우기/ 채우기

s = 0 #비우기
s = ( 1 << 21 ) - 1 # 채우기 10000..00000 - 1

 

비트마스킹 활용

~ 추가 예정 ~

주의사항

1.  int형 비트연산을 할때는  int형의 자릿수 32비트에서 부호비트 한자리를 제외한 31비트로 제한되어있어, 그 이상으로 연산을 하게되면 비트 값이 저장되지않을 수 있다. 
2. 비트 연산의 결과는 해당 자리의 비트에 대한 0,1이 반환되는 것이며 결과로 나오는 값은 해당 비트로 연산된 정수 값이지 0이나 1이 아니다.

if s & (1 << int(op[1])) != 0 :
	# do something
    
if s & (1 << int(op[1])) == 1 :
	# 잘못된 사용

 

 

비트 연산을 자유자재로 하는 그날까지 〰️➰ 열코🔆❗️

 

...

 

위 외판원 순회를 DP로 해결하기위해 비트마스킹을 사용해야만하는 이유를 간단하게 말해주는 블로그 하나 남기고 갑니당당..

https://real-012.tistory.com/86

[BOJ 2098] 외판원 순회(비트마스크, 자세한 설명)