네 반갑습니다. 이번 부록 C에서는 비트마스킹을 다뤄보겠습니다.

이번 강의에서는 간단하게 비트 연산자들을 살펴보고 비트마스킹을 익힌 후에 문제를 같이 풀어볼 예정입니다. 이것도 다른 부록들처럼 그렇게 양이 많지도 않고 어렵지도 않아서 약간은 편안한 마음으로 들을 수 있습니다.

일단 비트마스킹은 우리가 흔히 아는, 0과 1을 담고 있는 비트를 이용해서 연산을 효율적으로 하는 그런 방법을 말합니다. 자료구조라고 하기에는 너무 좀 거창한 것 같고 구현 기법 정도로 생각을 할 수 있습니다. 그래서 먼저 비트와 비트 연산자에 대해서 설명을 드리겠습니다. Drop the bit yeah

일단 먼저 1비트짜리에서의 비트 연산을 보겠습니다. 비트 연산은 AND(&), OR(|), XOR(^), NOT(~)이 있고 각각의 계산 결과를 확인해보세요. AND는 둘 다 1이어야 결과가 1이고, OR은 둘 중 하나라도 1이면 결과가 1이고, XOR은 둘 중 하나는 0이고 다른 하나는 1이면 결과가 1입니다. 마지막으로 NOT은 그냥 비트를 반전시키는 연산입니다. 여기서 AND와 OR은 조건문을 쓸 때 &&와 ||으로 작성을 많이 했다보니 익숙할텐데 XOR와 NOT은 아마 처음 봤을수도 있을 것 같습니다. 특히 XOR의 경우에는 ^ 이 기호가 지수승을 나타낼 때에도 많이 사용합니다. 그래서 아직 프로그래밍에 안 익숙한 사람이 2의 3승같은거 계산하고 싶을 때 2^3으로 쓴다음에 이게 왜 8이 아니지 하는걸 종종 봤던 것 같은데 C++에서 ^는 지수가 아니라 XOR입니다.

다음으로 앞에서 본걸 char에서 해보겠습니다. int나 long long도 똑같습니다. 0x01강 – 기초 코드 작성 요령 I에서 정수 자료형 관련해서 설명드린걸 잠깐 다시 봅시다. 이거 표 자체를 예전 ppt에서 그대로 가져온건데, 뭔가 4년 전의 저랑 지금의 저랑 미적 감각이 약간 다릅니다. 저때는 검정이랑 노랑이랑 섞으면 되게 명시성이 높다 해야하나 쨍하게 잘 보이니까 노랑 주황 이런걸 많이 썼는데 지금보니 좀 눈이 아픈 것 같기도 하고. 아무튼 char는 8개의 비트로 표현이 되는데 각 자리가 나타내는 값은 오른쪽부터 2^0, 2^1, .., 2^6, 그리고 제일 왼쪽에 -2^7이 있다는 그런 얘기를 했습니다. 그러면 9는 00001001로 표현이 가능합니다. 그리고 char에서 AND, OR, XOR, NOT과 같은 비트 연산을 한다고 치면 각 자리별로 그 연산을 수행을 하면 됩니다.

그러니까 되게 간단한건데, 예를 들어서 9 & 14라고 하면 9는 비트로 표현했을 때 00001001이고 14는 00001110입니다. 그러면 각 자리별로 &를 수행을 하면 되고 오른쪽에서 4번째 비트, 즉 8에 대응되는 비트만 1이 되어서 9 & 14 = 8입니다. 나머지 예시들도 한 번 확인을 해보시면 될거고, 여기서 NOT이 살짝 신기한 성질을 가지고 있는데, signed 자료형에서는 ~x = -x – 1입니다. 그러니까 ~16은 -17입니다. 이걸 어떤 관점에서 이해를 할 수가 있냐면 ~x와 x를 더했다 치면 각 비트가 다 1이 됩니다. x에서 0이었던 자리는 ~x에서 1이고 또 x에서 1이었던 자리는 ~x에서 0이기 때문에. 그리고 signed 자료형에서 11111111은 -1입니다. 그래서 ~x + x = -1이고 x를 넘기면 ~x = -x – 1이라는 식이 나옵니다. 일단 상황은 이렇고, 그런데 저는 사실 NOT을 잘 안써서 한번씩 남의 코드에서 NOT이 나오면 순간 이거 계산 결과가 어떻게 되더라? 하고 머리를 굴리곤 합니다. 그래서 좀 헷갈린다 싶으면 NOT은 굳이 안쓰셔도 상관은 없습니다.

그리고 다음으로는 쉬프트 연산인데, Left shift는 비트를 전체적으로 왼쪽으로 미는 연산입니다. 그러면 한 칸씩 밀 때마다 자연스럽게 값이 2배가 됩니다. 참고로 이 성질을 시뮬레이션 단원에서 감시라는 문제를 풀 때 잘 써먹었습니다. 그래서 9를 한 칸 밀면 18이 되고 3을 세 칸 밀면 3에다가 2^3 = 8을 곱한거라 24가 됩니다. 반대로 Right shift는 비트를 전체적으로 오른쪽으로 밀고, 이 때 값은 한 칸 밀 때마다 2로 나눠진다고 생각하면 됩니다. 또 이 때 나머지는 자연스럽게 버려집니다. 그런데 쉬프트 연산을 할 때 overflow를 굉장히 잘 신경써야 합니다. 예를 들어서 char 1을 왼쪽으로 7칸 밀면 이건 10000000일텐데 그러면 1 << 7 = -128인가? 혹은 1을 8칸을 밀면 1이 밀려나서 1 << 8 = 0인가? 뭐 이런 생각이 듭니다. 그런데 이렇게 뭔가 논리적으로 생각을 하면 1 << 7 = -128로 두고 1 << 8 = 0으로 두는게 그렇게 막 말이 안되는 것 같지는 않은데, 이게 C++ 버전에 따라서 값이 달라지거나 아니면 아예 Undefined behavior라고 해서 어떤 값이 나올지 정해져있지 않은 그런 상황이 될 수가 있습니다. 그래서 규칙을 완전히 정확하게 다 이해할게 아니라면 쉬프트 연산은 무조건 0과 양수에 대해서만 쓰고 overflow가 일어나지 않도록 하게 쓰는게 좋습니다. 저도 규칙이 헷갈려서 그냥 쉬프트 연산은 0과 양수 범위 안에서만 쓰고 있습니다. 정리를 하면 left shift는 그냥 2를 곱하는 연산, right shift는 2를 나누고 나머지를 버리는 연산이다. 그리고 무조건 무 적 권 0과 양수 범위 안에서만 놀게 하자. 로 요약이 가능합니다.

그리고 유의할 점이 한 개 더 있는데, 바로 연산자 우선순위에 관한 상황입니다. 표에서 위에 있을수록 높은 우선순위이고, 주황색 글씨는 비트 연산자를 의미합니다. 보면 비트연산자 말고도 연산자가 꽤 다양하다보니 표도 꽤 양이 많은데, 비록 이렇게 표로 제시한건 처음이라도 이 우선순위는 우리가 자연스럽게 체화를 하고 있었습니다. 예를 들어 a는 1보다 크고 b는 3보다 크다라는 조건을 if문 안에 쓰고 싶으면 자연스럽게 if(a > 1 && b > 3) 이라고 쓸 수 있는데, 논리 AND가 비교연산자 > 보다 우선순위가 높다는걸 알고 있기 때문에 굳이 a > 1과 b > 3에 괄호를 씌우지 않고 저렇게 표기를 해도 됐었습니다. 그런데 비트 연산자의 우선순위는 상대적으로 생소하고 이걸로 인해 코드가 의도한 것과 완전히 다르게 동작할 수 있습니다.  예를 들어서 a << 1과 b의 합을 계산하고 싶다면 무심코 a <<  1 + b로 써버릴 수 있는데, 표에서 볼 수 있듯 더하기가 left shift보다 우선순위가 높아서 의도와 다르게 a를 1 + b칸만큼 왼쪽으로 밀어버리는 상황이 나옵니다. 그렇기 때문에 저렇게 괄호를 쓰셔야 합니다. 또 다른 예시를 보면, a와 b & c가 같은지를 if문 같은 곳에서 확인하고 싶다고 할 때 a == b & c라고 쓰면 의도와는 다르게 a == b가 먼저 실행됩니다. 그래서 같으면 1, 다르면 0이 먼저 계산되고 그 값이 c와 &로 계산되는, 아마 절대 의도하지 않았을 이상한 무언가가 됩니다. 그렇기 때문에 이 경우에도 괄호를 쳐야 합니다. 사실 우선순위 자체는 충분히 헷갈릴 수 있습니다. 저도 매번 헷갈립니다. 대신 뭘 명심하면 되냐면, 잘 모르겠으면 무조건 괄호를 다 치셔야 합니다. 특히 비트연산자가 들어가면 그냥 묻지도 따지지도 말고 괄호를 다 쳐버리는걸 추천드립니다.

이제 기초는 다 다졌고 비트마스킹을 이해하기 위한 준비가 끝났습니다. 일단 하나 알고가면 좋은건 비트마스킹은 시간복잡도를 빅오의 관점에서 줄여주지는 않습니다. 예를 들어서 정렬은 그냥 막 짜면 O(N^2)이지만 머지 소트나 퀵 소트를 이용하면 O(NlgN)이었습니다. 그런데 비트마스킹은 이렇게 뭔가 빅오의 관점에서 시간복잡도가 개선되는건 아닙니다. 하지만 그렇다고 해서 비트마스킹이 의미가 없는건 아닌게, 맨 처음에 설명을 할 때 비트마스킹이 구현 기법이라고 했었습니다. 비트 연산자랑 비트마스킹에 충분히 익숙하다는 가정 하에 비트마스킹을 쓰면 우선 구현을 좀 더 깔끔하게 할 수 있습니다. 안 익숙하면 비트마스킹을 짠 코드를 볼 때 이게 무슨 외계어인가 싶을 수 있지만 익숙해진 다음에 보면 원래는 추가 변수도 쓰고 조건문 식도 복잡해질 상황을 되게 깔끔하게 처리할 수가 있습니다. 두 번째로 실제 속도랑 메모리에서도 이점을 챙길 수 있습니다. 상황이 잘 맞아떨어지면 64배 가까이 성능이 향상될 수가 있습니다. 물론 보통 코딩테스트 수준에서는 비트마스킹을 꼭 써야만 시간 제한이나 메모리 제한을 맞출 수 있게 출제를 하지는 않습니다. 그렇긴 한데, 어찌됐든 내 코드가 빨리 돌면 나쁠건 없습니다. 혹시 운이 좋으면 원래는 통과되어서는 안될 시간복잡도를 가진 잘못된 풀이가 비트마스킹을 끼얹어서 통과될 수도 있기도 하니까요. 그래서 비트마스킹이 뭐냐면, 0과 1만을 상태로 가지는 여러 값들을 정수 한 개로 관리하는 기법을 말합니다. 조금 있다가 뒤의 연습 문제들을 보시면 바로 이해가 가긴 할텐데 일단 지금 간단한 예시로 설명을 한번 드려보겠습니다.

뭘 할거냐면 집합 {0, 1, 2, 3}의 모든 부분집합을 구해보려고 합니다. 이건 백트래킹이나 시뮬레이션 단원에서 많이 하던거랑 비슷합니다. 백트래킹으로 구현을 하면  왼쪽처럼 짤 수가 있고 혹은 2진수 느낌으로 매번 2로 나누고 그 나머지를 가지고 처리하는 오른쪽 방법도 가능합니다. 지금 이 강의까지 오셨으면 두 방법 모두 충분히 익숙할거라고 생각해서 굳이 코드에 대한 설명은 하지 않겠습니다.  그런데 여기서 오른쪽 방법은 결국 tmp 변수를 2진수로 나타냈을 때 각 비트가 0이면 해당 비트에 대응되는 수를 없다고 생각하고 1이면 수를 있다고 생각하는 방법입니다. 그러니까 tmp가 13이라면 이건 2진수로 나타냈을 때 1101인데, 제일 오른쪽에 있는 비트부터 차례대로 0, 1, 2, 3에 대응을 시킵니다. 그렇게 되면 13은 부분집합 {0, 2, 3}을 나타내게 됩니다. 이걸 오른쪽처럼 지금까지 짜왔고 저렇게 짠다고 해서 문제가 있는건 전혀 아니지만 비트 연산자를 잘 활용하면 더 간결하게 코드를 짤 수가 있어서 어떻게 한다는건지 한번 보겠습니다.

다시 상황을 정리하면 tmp가 주어졌을 때 각 비트가 0인지 1인지를 판단할 수 있어야 합니다. 이건 앞에서 봤던 비트 연산자 중에 &를 이용하면 확인이 가능합니다. 먼저 제일 오른쪽에 있는 비트가 1인지 아닌지를 판단하려면 tmp를 0001과 AND 연산을 해보면 됩니다. 그렇게 되면 연산의 결과에서 제일 오른쪽 비트를 제외한 다른 비트들은 무조건 0이고, 제일 오른쪽 비트의 값에 따라 연산의 결과가 정해집니다. 즉 최종적으로 AND 연산의 결과가 0이면 제일 오른쪽의 비트가 0이고, 0이 아니면 제일 오른쪽의 비트가 1입니다. 다음으로 오른쪽에서 2번째 비트를 구하려면 이번에는 0010과 AND를 계산해보면 됩니다. 이 결과가 0인지 아닌지를 가지고 오른쪽에서 2번째 비트가 0인지 1인지를 구분할 수 있습니다. 그리고 나머지 남은 비트들은 각각 0100, 1000과 AND를 계산해보면 된다는걸 쉽게 눈치챌 수 있을 것입니다.

이 방법대로 구현을 하려면 0001, 0010, 0100, 1000을 계산해야 하는데 이건 left shift를 이용하면 됩니다. 1을 각각 0, 1, 2, 3칸 밀면 저 수들을 만들 수 있습니다. 최종적으로 코드를 짜보면 여기 func3처럼 구현이 가능합니다. 이전에 많이 했던, 수를 2로 나누고 나머지를 챙기는 방식으로 구현했던 func2와 비교를 해보면 직접 수를 나눌 필요가 없기 때문에 코드가 더 간결하고 또 func2에서의 brute와 같은 추가적인 변수가 필요없습니다. 물론 이 문제의 상황에서는 비트마스킹을 쓰지 않는다고 해서 크게 효율이 달라지지는 않기 때문에 만약 비트마스킹이 아직 익숙하지 않다면 비트마스킹을 이용해 이렇게 구현을 할 수 있다는 것만 확인하시고 계속 func2와 같은 방법으로 구현을 하셔도 상관은 없습니다. 하지만 뒤에서 같이 살펴볼 문제들은 비트마스킹을 활용했을 때의 이점이 있는 경우가 분명하게 있습니다. 이제 문제들을 같이 확인해보겠습니다.

이제 즐거운 문제 풀이 시간입니다. 첫 번째 문제는 BOJ 11723번 집합인데, 풀이가 아마 직관적으로 보입니다. 그냥 1부터 20까지의 각 값이 S 안에 있는지 여부를 저장할 20칸짜리 배열을 하나 잡고 연산들에 따라서 그걸 1 혹은 0으로 적절하게 바꾸면 됩니다. 메모리 제한이 4MB로 굉장히 작긴 하지만 이 방법을 쓰면 어차피 int 배열 20칸만 쓰는거니 크게 문제가 없습니다. 먼저 이렇게 구현을 해보겠습니다.

제 구현코드이고 크게 특별한건 없습니다. 뭐 생소할수도 있는 부분은 toggle에서 0이면 1로, 1이면 0으로 바꾸는걸 if문을 쓰는 대신 xor로 했다 정도? 다들 비슷하게 구현을 했을거라고 생각합니다. 그런데 물론 이 코드도 통과를 하긴 하는데 비트마스킹을 이용하면 더 개선을 할 수가 있거든요. 먼저 결국 state 배열의 각 칸은 딱 1비트만 차지하는데 그걸 위해서 4바이트씩 주는게 아깝다고 생각이 되니까 이걸 그냥 20비트짜리 수 하나만으로 상태를 나타내보자 하는 생각을 할 수 있습니다. 그런데 뭐 이 문제가 특별히 메모리를 엄청 적게 줘서 그렇지 보통 메모리는 차고 넘치니까 int 20개를 1개로 바꾸는게 엄청 큰 의미가 있지는 않아보입니다. 하지만 비트마스킹을 쓰면서 생기는 두 번째 장점은 아주 큰데, all과 empty 명령을 생각해보겠습니다. 지금 상황에서는 제가 작성한 코드처럼 그냥 20칸을 다 돌면서 1 혹은 0으로 바꾸는 방법이 최선입니다. 그런데 int 1개로 상태를 나타내면 all 명령은 상태를 2진수로 111...11, 즉 0xFFFFF로 변경하면 되고 empty 명령은
상태를 0으로 만들면 바로 끝입니다. 이렇게 되면 20번 대입 연산을 하던걸 딱 1번의 대입 연산으로 해결할 수 있습니다. 즉 all과 empty 명령을 20배 더 빠르게 할 수 있게됩니다. 그래서 state를 배열이 아니라 int 1개로 두고 각 비트에 적절하게 비트연산을 수행해서 문제를 푸는 비트마스킹 기법으로 코드를 짜보겠습니다.

일단 state가 int 1개로 바뀌고 각 명령들을 처리하는 방법도 달라졌는데, 하나씩 같이 살펴보겠습니다. 먼저 add를 보면 1 << (x-1)을 OR을 해주면 자연스럽게 해당 비트가 켜집니다. 다음으로 remove는 약간 복잡한데, 어떻게 생각을 하면 되냐면 만약 제일 오른쪽 비트만 끄고 나머지는 그대로 유지를 하고 싶다면 11111..110과 AND를 하면 됩니다. 그러면 나머지 다른 모든 비트는 원래 자기 자신의 값을 그대로 가지는데 제일 오른쪽 비트는 0이 됩니다. 그리고 제일 오른쪽에서 두 번째 비트만 끄고 싶으면 11111..101과 AND를 하면 돼요. 그럼 이 때 111111..110 혹은 11111..101과 같은 값을 만들려고 1 << (x-1)의 NOT을 계산합니다. 그래서 최종적으로 ~(1 << (x-1))과 AND를 계산하면 오른쪽에서 x-1번째 비트를 끌 수 있습니다.

다음으로 check인데, 부분집합을 출력하는 문제에서는 AND를 계산하는 값을 각 비트에 따라 0001, 0010, 0100, 1000 이렇게 왼쪽으로 밀었는데 지금은 출력이 0 혹은 1로 되어야 해서 state를 오른쪽으로 밀고 1과 AND를 계산하게 했습니다. toggle은 1 << (x-1)과 XOR을 하면 되고, 마지막으로 all과 empty는 각각 state를 0xfffff와 0으로 업데이트를 하면 됩니다. 이렇게 int 1개만 써서 state를 표현하고, 비트마스킹으로 적절하게 처리가 가능합니다. 다만 실제 실행 시간은 앞의 풀이와 지금 풀이가 크게 차이가 없는걸 확인할 수 있는데, 입출력 양이 많아서 실행 시간의 대부분이 입출력 처리에 쓰여서 그렇습니다. (코드)

두 번째 문제도 한 번 확인해봅시다. (링크) 일단 비트마스킹에 연연하지 말고 풀이를 한다고 하면 되게 간단하게 해결이 가능합니다. 2^N개의 각 가능한 기타 조합에 대해서 해당 조합이 몇 개의 곡을 연주할 수 있는지를 확인하면 끝입니다. 즉 문제를 부분 문제로 나눠보면 2^N개의 기타 조합 만들기,  조합이 몇 개의 곡을 연주할 수 있는지 확인하기 이렇게이고, 각각이 모두 비트마스킹을 이용해서 최적화를 할 수 있습니다. 2^N개의 기타 조합을 만드는건 앞에서 이미 같이 본거니까 생략하고 조합이 몇 개의 곡을 연주할 수 있는지를 어떻게 처리할지 고민해보겠습니다. 먼저 기타가 연주할 수 있는 곡의 목록이 YYYNN과 같은 방식으로 주어지는데, 이걸 string으로 저장하지 말고 앞의 문제에서 state와 같이 정수 하나에 넣습니다. 문제의 제한조건 상으로 M이 최대 50이니 32비트인 int에는 다 담을 수가 없고 대신 long long을 쓰면 됩니다. 즉 YYYNN은 이진수 11100으로 만들어서 곡의 목록을 11100 = 28으로 저장합니다. 그리고 내가 선택한 기타 조합이 몇 개의 곡을 연주할 수 있는지는 이 state들을 가지고 어떤 적절한 비트연산자를 적용하면 되는데, 딱 하나의 기타만이라도 1이면 그 곡을 연주할 수 있는거니까 이건 OR입니다. 즉 state들을 다 OR을 한 결과에 있는 1의 개수가 바로 조합이 연주할 수 있는 곡의 개수입니다. 이제 구현을 직접 해보겠습니다.

일단 저는 bit_cnt라고 하는, long long 인자가 주어지면 거기에 있는 1의 개수를 반환해주는 함수를 하나 만들었습니다. 그리고 state[i]는 i번째 기타가 연주할 수 있는 곡의 정보를 정수 하나로 나타낸 값인데, 앞에서 설명했듯이 곡이 최대 50개여서 반드시 long long으로 선언을 해야합니다. 그리고 21번째 줄에서 저렇게 YYYNN 이런 입력받은 값을 가지고 state[i]를 구성할 때 state[i]를 left shift로 왼쪽으로 한 칸씩 밀면서 OR을 하는건 되게 많이 쓰이는 방법이라 눈에 한 번 익혀갑시다. 25번째 줄은 2^N가지 조합을 다 돌리기 위한 for문이고 28-30번째 줄처럼 비트가 켜져있는 기타들에 대해 state를 전부 OR 연산을 해줍니다. 최종적으로 그렇게 구해진 comb 변수에 있는 1의 개수를 구해서 적절하게 처리를 하면 끝입니다. 한 가지 실수하기 쉬운 점은 28번째 줄에서 (1LL << i) 부분인데, tmp의 i번째 비트가 켜져있는지를 확인하기 위해 1 << i를 계산하면 됩니다. 그런데 그냥 1은 int이고, 이걸 32칸 이상 왼쪽으로 밀면 오버플로우가 납니다. 차라리 컴파일이 안되면 빨리 알아차릴 수가 있는데, 실행은 잘 되지만 정작 결과가 이상해지고 심지어 곡이 32개 이상 있어야 오류를 발생하니 하필 예제는 다 잘 통과되어서 오류를 찾는데 꽤 오랜 시간이 걸리게 됩니다. 아무튼 left shift를 최대 50까지 해야하기 때문에 1을 long long으로 바꿔야 하고 그래서 (1LL << i)로 코드를 짜야 합니다. (코드)

네 이번시간에는 이렇게 비트마스킹을 같이 살펴봤습니다. 비트 연산자에 익숙하다는 가정 하에 비트마스킹은 메모리와 성능 모두에 이득을 줄 수 있어서 구현 기법 중 하나로 익혀두면 분명 도움이 되는 순간이 있을 것입니다. 다만 보통 비트마스킹을 꼭 써야만 시간 혹은 메모리 제한을 맞출 수 있는 경우는 잘 없어서 나는 도저히 이 비트 연산자들이 낯설고 정이 안간다라고 하면 뭐 굳이 안하셔도 상관은 없습니다. 강의를 만든 제 입장에서는 아쉽긴 하지만. 본인이 종사하고자 하는 분야가 로우 레벨 쪽이면 꼭 비트미스킹이 아니더라도 비트 연산자를 볼 일이 많을거라 이번 기회에 겸사겸사 비트 연산자와 친해져보시고, 나는 로우 레벨은 아니다 하면 그래도 이게 그렇게 막 어려운건 아니니까 한 번 익혀보시면 좋겠지만 도저히 비트 연산자를 쓰기 싫다라고 하면 그냥 시뮬레이션 단원 느낌으로 문제들만 가볍게 한 번 풀어보시고 넘어가셔도 괜찮습니다. 그럼 고생 많으셨습니다. 안녕~