컴퓨터는 모든 정보를 이진법으로 저장하고 대부분의 언어는 비트 단위 연산을 지원한다. 즉 int는 32비트짜리, long long은 64비트짜리 공간이므로 이를 각각 크기 32 혹은 64의 bool 배열로 생각할 수 있다.
변수 x를 비트마스킹으로 bool의 배열로 생각할 경우, k번째 성분의 값 x & (1 << k)로 확인할 수 있다. 만일 x의 k번째 비트가 참이라면 x & (1 << k)는 1 << k가 될 것이고, 그렇지 않다면 0이 되기 때문이다. 같은 논리로 k번째 값을 true로 설정하는 것은 x |= (1 << k), false로 설정하는 것은 x &= ~(1 << k)로 실행할 수 있다. 또 비트마스킹 문제 중 조건에 true로 바꾸는 연산은 기존값이 false임이, false로 바꾸는 연산은 기존값이 true임을 보장할 수 있다고 되어있는데, 이 경우 or 혹은 and 연산을 xor로 대체하여 x ^= (1 << k)로 나타낼 수 있다.
https://www.acmicpc.net/problem/1094
1094번: 막대기
지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대
www.acmicpc.net
https://www.acmicpc.net/problem/18119
18119번: 단어 암기
준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주
www.acmicpc.net