비트마스크 알고리즘

728x90

도입

비트마스크 알고리즘은 비트연산자를 활용해 간단하게 집합을 표현하는 알고리즘이다.

비트마스크를 사용하면 하나의 정수로 여러가지 집합을 표현할 수 있다. 하지만 여러가지 제약사항이 있으므로 사용에 있어 주의해야하며 주로 다이나믹 프로그래밍에서 주로 사용한다.

| 연산 : or연산으로 둘 중 하나가 1이면 1이다.

&연산 : and연산으로 둘 다 1이어야 1이다.

^연산 : xor연산으로 두개의 연산자가 서로 다른 값이어야 1이다.

~연산 : not연산으로 1을 0으로 0을 1로 변경하여준다.

-shift연산-

>> 연산은 비트를 오른쪽으로 미는 연산으로 2의 n승을 나누는 것과 동일한 결과가 나온다.

<< 연산은 비트를 왼쪽으로 미는 연산으로 2의 n승을 곱하는 것과 동일한 결과가 나온다.

비트마스크는 위에서 설명한 연산들을 활용하여 집합을 표현하고 삽입, 삭제, 유무 등등을 하나의 정수로 표현하는 알고리즘이다.

비트연산자는 0~N사이의 값을 지닌 집합을 표현할 때 사용하며, 배열의 인덱스로도 적용할 수 있다. 0부터 N까지 각각 1개의 비트씩 연결을 하여 m번째 비트가 1이면 m이라는 숫자는 집합에 있다는 것을 의미하도록 표현한다.

비트마스크의 장점은 집합의 삽입, 삭제 그리고 찾기를 모두 시간복잡도 O(1)에 해결할 수 있다는 장점이 있다.

하지만 단점으로는 N값이 너무 크게 되면 사용이 불가하다.(32bit의 정수를 사용하는데 33개의 수를 가진 집합이면 표현을 못함)

비트마스크를 구하기 위해 삽입, 삭제, 찾기를 구현해보자. 집합을 의미하는 비트마스크 숫자를 bit이라고 표현하여 설명하도록 하겠다.

삽입을 하는 연산을 구현하기 위해 우리는 '|'연산을 사용한다. 삽입을 할 위치를 1로 설정하여 | 연산을 해주면 만약 있더라도 추가가 되지 않고, 없다면 1로 바뀔 것이다.

bit = bit | (1 << a) // 만약 3을 넣고싶으면 a = 4 (0부터 시작하므로)

삭제를 하는 연산을 구현하기 위해 우리는 '&' 연산을 사용한다. 절대로 '-'를 사용해서는 안된다. 삭제할 값을 1로 설정하고 not연산자로 모두 뒤집어 주어 연산을 수행한다.

bit = bit & ~(1 << a) // 삭제

찾는 연산도 삭제를 하는 연산과 동일한데 not연산자를 사용하지 않습니다. 만약 해당 값이 있다면 1 없다면 0이 나오게 됩니다.

bit = bit & (1 << a) // 1이면 있음 0 이면 없음
(bit >> a) & 1 // 반대로 생각할 수 도 있음.

항상 주의해야할 점은 연산자의 우선순위를 잘 고려해야한다. 우리가 사용하는 사칙연산의 경우 곱셈과 나눗셈이 당연 덧셈과 뺄셈보다 먼저 될 것이라고 알고있다. 하지만 비트 연산자는 우선순위를 매번 외우는 것도 힘드므로 무조건 괄화를 활용하여 처리해야한다.

두번째로 주의할 점은 항상 0부터 시작된다는 것이다. 첫번째 비트가 가리키는 부분은 항상 0임을 명심하고 구현해야한다.

1. 비트마스크는 집합을 정수로 표현하여 메모리를 아끼고 시간복잡도상 O(1)이라는 매우 빠른 속도를 보여주는 알고리즘이다.

2. 비트마스크는 연산자 우선순위를 잘 고려하여 작성을 해야한다.

728x90