Algorithms (2) 썸네일형 리스트형 [python] 비트마스킹 ***비트마스킹 : 정수로 표현된 2진수 숫자 자체를 자료구조로서 활용하는 것 일반적인 코딩테스트 문제에서, 경우의 수 30-31 가지 이상의 상황에서는 비트마스킹을 활용하기 어렵습니다. 시간복잡도의 문제로 시간초과가 나기 쉽기 때문입니다. ( 2^30 = 1,073,741,824 ) 그럼에도 불구하고 비트연산을 활용하면 다른 자료구조를 사용했을 때보다 획기적으로 연산 시간을 줄 일 수 있을 때가 많습니다. 또한 펜윅트리에서 비트마스킹은 매우 유용합니다. 1. 비트 연산자 AND & ( 1 & 1 == 1 ) OR | ( 1 | 0 == 1 ) ( 1 | 1 == 1 ) XOR ^ ( 1 ^ 0 == 1 ) ( 1 ^ 1 == 0 ) NOT ~ ( ~1010 == 0101 ) [SHIFT] 1 1 2 >.. [cpp] 비트마스킹 옛날에 비트마스킹을 공부할 때 정리했던 노트입니다. "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"(도서, 구종만 저)과 백준의 "집합" 문제를 참고하여 작성했던 자료입니다. 중요한 자료는 아니지만 혹시 필요하신 분이 계실 까봐 업로드해두었습니다. 이전 1 다음
