(사진은 우리집 강아지ㅎㅎ)
비트 마스크.... 나도 잘 안 쓰는 방식이긴 하다.
근데 가끔 비트 마스크로 풀면 잘 풀리거나 메모리 초과를 방지할 수 있는 문제들이 있다.
음... 예를 들면 경로를 탐색하는데 각 노드를 방문할때 어떤 상태로 방문하는지 알아야하고, 그 방문 상태를 노드가 가지고 있어야할때를 들 수 있을거 같다.
(백준에 문제가 있는데... 나중에 생각나면 링크 걸어야겠다.)
일단 Bit mask를 포스팅해야겠다고 마음 먹은 문제는 LeetCode: Single Number 이거이다.
문제를 다루기 전에 bit mask에 대해서 알아보자!
비트 마스크는 이름에서 알 수 있듯 bit에 관련한거다.
bit란 무엇일까?
- 컴퓨터에서 사용되는 데이터의 최소 단위
- 0과 1을 값으로 가진다.
"0, 1 두개의 값만 가진다"에서 이진법이 떠오른다.
(나만 그럴 수 있음...)
13 = 1101
(이진수 변환에 대해서는 생략하겠다.)
위처럼 13인 십진수를 1101인 이진수로 변환할 수 있다.
우리는 bit가 0과 1의 값만 가지고 있음을 알고, 이진수도 0과 1의 값만 가지고 있음을 알고 있다.
bit mask란 무엇일까?
비트마스크는 이런 bit를 활용한다.
즉, 정수의 이진수 표현을 활용한 기법이다.
비트 마스크를 활용하는 대표적인 예를 통해 이해해보자!
[0, 1, 2, 3, 4, 5]라는 요소를 가진 배열이 있다.
우리는 여기서 요소 몇 개를 선택하고 어떤 요소를 선택했는지 표현하고 싶다.
(보통 PS에서는 dfs 문제 형태에서 많이 나오는 유형이다.)
비트 마스크를 사용하지 않고 푼다면
boolean 배열을 통해 요소를 선택했는지 아닌지 표시할 수 있다.
{0} = [true, false, false, false, false, false]
{0, 1} = [true, true, false, false, false, false]
{0, 1, 2} = [true, true, true, false, false, false]
...
이런식으로 표현할 수 있다.
하지만 이 방식은 메모리를 많이 차지하고 오버헤드가 증가한다.
비트 마스크를 사용해 푼다면
{0} = 0번째 index가 true = 000001
{0, 1} = 0번째 index, 1번째 index가 true = 000011
{0, 1, 2} = 0번째 index, 1번째 index, 2번째 index가 true = 000111
...
이런식으로 표현할 수 있다.
즉, 배열 i번째 요소가 선택되었다면 1이 된다.
그렇다면 위와 같은 이진수를 십진수로 바꿀 수 있지 않을까?
당연히 된다.
{0} = 0번째 index가 true = 000001 = 1
{0, 1} = 0번째 index, 1번째 index가 true = 000011 = 3
{0, 1, 2} = 0번째 index, 1번째 index, 2번째 index가 true = 000111 = 7
...
이런 식으로 부분집합을 배열이 아닌 정수를 통해 나타낼 수 있다.
즉, 7이라는 정수는 [0, 1, 2, 3, 4, 5] 배열에서 {0, 1, 2}를 선택한 것이다.
그렇다면 {0, 1, 2} 부분집합에 5를 추가하고 싶다면 어떻게 하면될까?
000111 | (1 << 5)
위의 방법을 통해 추가할 수 있는데 하나씩 살펴보도록 하자
비트 연산
AND 연산 (&)
대응하는 두 비트가 모두 1일때 1을 반환
1010 & 1111 = 1010
OR 연산 (|)
대응하는 두 비트가 하나라도 1일때 1을 반환
1010 | 1111 = 1111
XOR 연산(^)
대응하는 두 비트가 서로 다르면 1을 반환
1010 ^ 1111 = 0101
NOT 연산(~)
비트의 값을 반전하여 반환
~1010 = 0101
Shift 연산(<<, >>)
왼쪽 또는 오른쪽으로 비트를 이동한다.
00001010 << 2 = 101000
00001010 >> 2 = 000010
그렇다면 이 비트 연산을 어떻게 활용할 수 있을까?
비트 연산 활용
추가
i(5) 번째 수를 추가
000111 | (1 << 5)
= 000111 | 100000
= 100111
삭제
i(5) 번째 수를 삭제
100111 & ~(1 << 5)
= 100111 & ~(100000)
= 100111 & 011111
= 000111
조회
i(2) 번째 수가 있나 없나 확인 (있다면 1이상, 없다면 0)
000111 & (1 << 2)
= 000111 & 000100
= 000100
= 4
i(3) 번째 수가 있나 없나 확인
000111 & (1 << 3)
= 000111 & 001000
= 000000
= 0
토글
i(2) 번째 수가 켜져 있으면 끄고, 꺼져 있으면 킴
000111 ^ (1 << 2)
= 000111 ^ 000100
= 000011
(2번째가 1에서 0으로 바뀐 것을 확인)
i(3)번째 수가 켜져 있으면 끄고, 꺼져 있으면 킴
000111 ^ (1 << 3)
= 000111 ^ 001000
= 001111
(3번째가 0에서 1로 바뀐 것을 확인)
문제 활용
그럼 내가 비트 마스크로 푼 문제(LeetCode: Single Number)를 통해 비트 연산을 활용해보자.
사실 이 문제는 거창하게 비트 연산을 사용한건 아니지만 문제를 풀면서 비트 연산을 사용한 문제는 여기에 링크를 추가해 나가겠다.
풀어야하는 문제는 간단하다.
배열 A가 주어지고, A에서 짝이 없는 수를 찾는 문제이다.
[2, 2, 1, 4, 5, 5, 4]라면 정답은 1이다.
다른 숫자들은 각각 pair가 있기 때문이다.
물론 다양한 풀이법이 있을 수 있다.
나도
1. ArrayList로 pair를 확인하는 방법
2. A를 정렬해서 pair를 확인하는 방법
으로 풀었었다.
public int solution(int[] A) {
Arrays.sort(A);
for(int index = 1; index < A.length; index += 2) {
if(index == A.length - 1) {
return A[index];
}
if(A[index] != A[index - 1] {
return A[index];
}
}
}이런 코드로 풀었었다.
비트 마스크로 문제 풀기
우리는 위에서 비트 마스크로 토글하기에 대해서 살펴봤다.
이 방법을 통해 문제를 풀어볼거다.
우선, 주어진 문제는 짝수개가 아닌 수를 반환하면 된다.
전구를 클릭해서 켜고 끈다고 생각해보자.
전구를 홀수번 클릭하면 전구의 상태는 켜져있다.
전구를 짝수번 클릭함녀 전구의 상태는 꺼져있다.
이 아이디어를 차용해서 우리가 구하려는 수도 만약 짝수개라면 0이될 것이고, 홀수개라면 1이 될 것이다.
public int solution(int[] A) {
int n = 0;
for(int a : A) {
n ^= a;
}
return n;
}그래서 내가 사용한 코드는 위와 같다.
