[코테, 알고리즘] 백준 class 3 - 비트마스크

[11723] 집합

문제자체는 쉽지만 저 아주 빡도는 메모리 제한을 보라!! 무려 꼴랑 4MB!!

~해서 비트마스크로 풀어야하는데 처음이라 뭔지 모르겠어서 우왕좌왕하다가 정리해본다.

비트마스크를 이용한 집합 구현

N비트 정수 = N개의 원소를 갖는 집합
하나의 bit = 하나의 원소
1 = 집합에 포함되어 있다
0 = 집합에 포함되어있지 않다

💡 N개의 원소를 가지는 집합을 표현할때, N개의 boolean 원소를 갖는 배열을 선언하는 것이 아니라, N비트 정수 1개로 표현하는 것이 중요한 포인트!!
💡 문제에서 메모리 제한이 4MB인것도 정수형 변수의 메모리가 4MB라서 인거임
💡 32비트(or 64비트)가 넘어가면 오버플로우 발생하니 조심!

1. 공집합

S = 0

2. 꽉 찬 집합

S = (1 << N) - 1

ex) 6비트 정수로 꽉 찬 집합을 만들려면?

3. 원소 추가하기

S = S | (1 << K)

ex) S = 100000(2) 일때 3을 추가하고 싶다면?

4. 원소 삭제하기

S = S & ~(1 << K)

ex) S = 101000(2) 일때 3을 삭제하고 싶다면?

5. 원소 토글하기

S = S ^ (1 << K)

ex) S = 101000(2) 일때 3을 토글하고 싶다면?

6. 원소의 포함여부 확인하기

if S & (1 << K):
	포함 O
else:
	포함 X

ex1) S = 101000(2) 일때 3이 포함되어있는지 확인하려면?

ex2) S = 100000(2) 일때 3이 포함되어있는지 확인하려면?