브루트 포스 - 비트 마스크

not 연산을 하는 경우에는 자료형에 따라 달라 진다.

정수로 집합을 나타낼 수 있다. int 는 32비트 이기 때문에 2^32 즉, 4294967296을 넘어서면 안된다.

비트 마스크는 0~n-1 의 정수로 이루어진 집합을 나타낼 때 사용한다!! 1~n까지 정수는 공간이 2배 더 필요하다!!

각종 연산

전체 집합 : (1<<N) -1 -> { 0,1,2,... , N-1}
공집합 : 0
현재 집합이 S일 때,
i를 추가 : S | (1<<i)
i를 검사 : S & (1<<i)
i를 제거 : S & ~(1<<i)
i를 토글 : S ^(1<<i)

물론 배열을 사용하는 것이 편리하지만, 집합을 배열의 인덱스로 나타낼 수 있기 때문에 비트 마스크를 사용!!!

비트 마스크의 시간 복잡도는 o(2^n) 이므로 주의 해서 사용...부분수열의 개수가 2^n 개이기 때문..

• [1182],[14889][14391] 모두 크기가 기껏해야 10 언저리..