기타

비트마스킹

비트마스크란? 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료구조로 쓰는 기법이다. 이진수는 0 또는 1을 이용하므로 두 가지로 표현할 수 있다. 장점 수행 시간이 빠르다. (bit 연산은 O(1)에 구현되는 것이 많다.) 코드가 짧다. (다양한 집합 연산들을 비트연산자로 한 줄로 작성할 수 있다.) 메모리 사용량이 적다. (가장 큰 장점, DP에 매우 유용하게 쓰임.) 비트 연산자 종류 AND 연산 (a&&b) → 대응하는 숫자가 모두 1이면 1 반환 OR 연산 (a||b) → 대응하는 숫자 중 하나라도 1이면 1 반환 XOR 연산 (a^b) → 대응하는 숫자가 서로 다를 경우 1 반환 NOT 연산 (~a) SHIFT 연산 (>>,