알고리즘) 비트마스크 - 브루트 포스

# 비트마스크
 - 비트 연산을 사용해서 부분집합을 표현하는 하나의 방법

# 비트 연산
and(&), or(|), not(~), xor(^)

비트연산의 시간복잡도 : O(1)

cf) not의 비트연산은 자료형에 따라 결과가 달라진다.
ex) 8bit 자료형, 32비트 자료형의 결과가 다르다. 
A = 1010011이면
~A = 10101100 (8비트)
~A = 11111111 11111111 11111111 10101100 (32비트)

# shift 비트연산 : right shift(>>), left shift(<<)
ex) 

1<<4 = 10000 (16)
1010 >> 3 = 1 (1)

A<<B는 A*(2^B)와 같고
A>>B는 A/(2^B)와 같다.

# 비트 연산
 - 정수를 이용해서 집합을 나타낼 수 있다.
{1, 3, 4, 5, 9}가 있다면
1을 2^1, 3을 2^3, 4를 2^4, 5를 2^5, 9를 2^9로 놓고
모두 더한 값인 570으로 해당 집합을 나타낼 수 있다.
{1, 3, 4, 5, 9} = 2^1 + 2^3 + 2^4 + 2^5 + 2^9 = 570


장점 : 정수 1개로 집합을 표현할 수 있으므로 공간적으로 효율적이다.

cf) 비트마스크를 사용하기 위해서는 사용하려는 수가 최대 몇개가 있는지 알아야 한다.
(int 자료형의 경우 32비트이기 때문에 2^32가 넘는 수를 사용하는 집합은 표현할 수 없음)

비트마스크 사용 시에는 n개의 수를 0부터 n-1로 변환하여 사용하는 것이 좋다.

(1~n으로 사용하면 0~n-1에서 1만큼 left shift한 것인데 이는 곧 *2를 한 것으로

공간적으로나 시간적으로나 2배가 소요된다.)

# 비트마스크에서 수를 포함하는지 검사하는 방법
ex) {1, 3, 4, 5, 9} = 570 = 1000111010
2가 포함되어 있는지 검사 -> 1000111010에 2^2자리를 포함하고 있는지 확인해야 한다.
570 & 2^2 = 570 & (1<<2) = 0 
1. 1<<2 : 2^2자리를 1로 설정
2. 570 & (1<<2) : 2^2자리끼리 and 연산을 했을 때, 
결과가 2^2이면 570도 2^2자리가 1인 것이고 결과가 0이면 570은 2^2자리가 0인 것이다.

# 비트마스크에서 수 추가 연산
ex) {1, 3, 4, 5, 9} = 570 = 1000111010
추가하려는 수의 비트 위치를 1로 바꾸어주면 된다.
2를 추가하려면 570 | (1<<2) = 574
1000111010 에 100을 or 연산한 것으로 2^2의 자리가 무조건 1이 된다.
결과 : 1000111110

같은 것을 또 추가한다 하더라도 연산 결과가 같기 때문에 중복처리 가능 (or연산의 특징)

# 비트마스크에서 수 제거 연산
제거하려는 수의 비트 위치를 0으로 바꾸는 것이다.
1을 제거하려면 570 & ~(1<<1) = 568
1. ~(1<<1) 은 2^1자리만 0인 2진수를 만들어준다
2. 570 & ~(1<<1) 은 570에서 1번에서 만든 2진수와 and연산을 수행하므로
 해당 2진수에서 0인 2^1자리를 570에서도 0으로 만든다.

# 비트마스크에서 수 토글 연산
1을 토글하기 570 ^ (1<<1)
xor 비트 연산을 사용 1^1 = 0, 1^0 또는 0^1 = 1이 되는 특성 사용
570의 해당 자리가 1이였다면 1^1 연산이 되어 0으로 토글되고
해당 자리가 0이였다면 1^0 연산이 되어 1로 토글된다.

# 비트마스크의 전체 집합 = (1<<N)-1 = 2^N -1 개
# 공집합 = 0 (모든 수들이 0 -> 결과 값도 0이 됨)

# 비트연산 정리
 - i 추가 : S | (1<<i)
 - i 존재 검사 : S & (1<<i)
 - i 제거 : S & ~(1<<i)
 - i를 토글 : S ^ (1<<i)

# 비트마스크를 언제 사용하는가?
문제에 할 수 있는 것이 n개가 있고, 이때 일부를 선택해서 할 수 있을 때
모든 경우를 만드는 경우

ex) 부분 집합의 합

www.acmicpc.net/problem/1182

1182번: 부분수열의 합