비트마스크(1)

카카오 코테를 풀어보면서, DFS로 인해 복잡한 코드를 비트마스크를 통해서 간단하게 구현한 코드를 보게 되었습니다.
이전에 알고리즘 스터디를 할 때 스터디원 한 분이 비트마스크를 활용해서 풀었다고 했을 때, 배워봐야지 생각은 했는데 이제서야 학습하네요. 처음 개념 공부를 할 때에는 블로그를 찾기보다는 책으로 공부하는 편이기 때문에 '알고리즘 문제 해결 전략' 책을 읽고 정리한 것입니다.
처음 읽었을 때 이해가 안되서 두 번 계속 읽어본 결과, 여전히 낯설고 어려운 개념입니다 ㅎ
초반에는 읽고 바로 기초 문제들을 풀 수 있겠지 싶어서 호기롭게 도전했는데, 쉽지가 않네요..
아직도 약간은 기초 문제를 풀기조차 힘든 부족한 부분이 있는 것 같아요.
그래서 일단 정리를 해두고 다음주(~2023.03.21)까지의 목표는 비트마스크 문제를 집중적으로 공략해보기로 정했어요.

개념 정리

비트마스크의 도입 배경

현대의 모든 CPU는 이진수를 이용하여 모든 자료를 표현합니다.
덕분에 내부적으로 이진법 관련 연산을 빠르게 할 수 있는데요. 이런 특성을 활용해서 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 부릅니다.

비트마스크를 도입함으로써 얻을 수 있는 장점에는,
1. 더 빠른 수행 시간
비트마스크 연산은 O(1)에 구현되는 것이 많습니다. 그래서 적절히 사용한다면, 훨씬 빨리 동작할 수 있어요.
그러나, 비트마스크를 사용할 수 있다는 건 원소의 수가 많지 않다는 뜻이기 때문에 눈에 띄는 속도 향상을 기대할 수는 없다고 합니다.
비트마스크 연산을 굉장히 여러 번 수행해야 할 경우에는 작은 최적화도 큰 속도 향상을 가져올 수 있습니다.
저는 이 부분에서 비트마스크 연산은 원소의 수가 많지 않을 때 사용할 수 있다는 인사이트를 얻을 수 있었습니다.

2. 더 간결한 코드
3. 더 작은 메모리 사용량
4. 연관 배열을 배열로 대체
이렇게 4가지의 장점을 제시할 수 있어요.

 

비트 마스크 용어 정리

비트(bit)란 이진수의 한 자리 말합니다. 

비트는 0 혹은 1의 값을 가질 수 있고, 컴퓨터가 표현하는 모든 자료의 근간이 됩니다.

부호없는 8비트 정수형은 8자리의 이진수로서 표시할 수 있는 모든 정수를 표현할 수 있습니다.

최소값(0)부터 최대값(1111 1111(2) = 255)까지 값을 가질 수 있습니다. 

 

위의 부호없는 8비트 정수형 예시처럼, 부호 없는 N비트 정수형 변수는 N자리의 이진수로 사용할 수 있습니다. 

각 비트가 표현하는 값은 맨 오른쪽부터 2^0 ~ 2^(n-1)까지입니다. 

2^(n-1)에 해당하는 비트를 최상위 비트(MSB, Most Significant Bit)라고 부르고,

2^0에 해당하는 비트를 최하위 비트(LSB, Least Significant Bit)라고 부릅니다.

 

정수를 이진수로 표현했을 때, 비트의 위치가 1이라면 해당 비트가 "켜져있다"라고 말하고,

비트의 위치가 0이라면 해당 비트가 "꺼져있다"라고 말합니다. 

 

비트 연산자(AND, OR, XOR, NOT, 시프트)

두 정수 변수(a,b)를 비트별로 조작할 수 있는 비트 연산자를 사용해야 합니다.

AND는 모두 켜져있을 때만(=비교하는 비트들이 모두 1일 때만) 결과로 나타낼 비트를 킵니다. - a & b

OR은 두 비트 중 하나라도 켜져 있을 때만(=비교하는 비트들 중 최소 하나가 1일 때만) 비트를 킵니다. - a | b

XOR은 하나는 켜져있고, 하나는 꺼져있는 특수한 상황에서 비트를 킵니다. - a ^ b

NOT은 꺼져있는 비트는 켜고, 켜져있는 비트는 끕니다(1 -> 0, 0 -> 1) - ~a

시프트(shift)는 정수 a의 비트들을 왼쪽 또는 오른쪽으로 c비트만큼 움직입니다.