비트란?
컴퓨터에서 사용하는 데이터의 최소 단위
0과 1
비트마스크란?
정수의 이진수 표현을 자료 구조로 쓰는 기법
집합을 메모리/시간 효율적으로 표현 가능하게 해줌
ex) 집합의 i번째 요소가 존재한다면 1, 존재안하면 0으로 표시 (비트마스킹)
비트 연산자 종류
-and 연산 &
-or 연산 |
-xor 연산 ^
둘 중 하나만 1일 때 1
-not 연산 ~
-shift 연산 <<, >>
왼쪽, 오른쪽으로 비트 이동, 빈자리는 0으로
비트마스크 연산 활용
-부분집합 i번째에 요소 삽입(i번째 비트 1로)
bit=bit | 1<<i
-부분집합 i번째 요소 삭제(i번째 비트 0으로)
bit=bit & ~(1<<i)
-부분집합 i번째 요소 조회
if ( bit& (1<<i)==1 ) i는 1
else i는 0
-부분집합 i번째 요소 토글(0->1,1->0)
bit=bit ^ ( 1<<i )
비트 마스크 사용시 주의할 점
-비교 연산자보다 비트 연산자의 우선 순위가 낮음
-오버플로우 문제
비트마스크의 장점
1. 빠른 수행속도
O(1)
2. 코드가 짧음
집합 연산들을 비트연산자를 활용해 한 줄로 표현 가능
3. 적은 메모리 사용량
4. 집합을 배열의 인덱스로 활용할 수 있음
참고사이트
https://jooncco.com/algorithms/bitmask/
https://kim6394.tistory.com/246
'cs > 알고리즘' 카테고리의 다른 글
| [알고리즘 문제 유형] 문제에서 알고리즘 문제 유형 파악하기 (0) | 2022.02.25 |
|---|---|
| [알고리즘] 재귀(recursion) (0) | 2022.01.21 |
| [알고리즘] 동적 계획법 (dynanmic programming) (0) | 2021.09.26 |
| C++ 실행 속도 향상 ios_base::sync_with_stdio(0); cin.tie(NULL); (0) | 2021.09.18 |
| [알고리즘] 브루트 포스(Brute Force) (0) | 2021.09.12 |