728x90
비트마스크 (BitMask)
- 정수로 집합을 나타낼 수 있는 기법
비트마스크를 사용하는 이유
- 완전 탐색 시 재귀호출 없이 모든 경우를 살펴볼 수 있다. (브루트 포스)
- 집합을 배열의 인덱스로 표현 가능하다. → 메모리 절약 가능
- 상태가 다이나믹한 경우에 자주 사용한다.
연산
1. 포함 검사
- '&' 사용
- 집합 S에 i가 포함되었는지 검사 : S & (1 << i)
- 0 : 미포함
- 2 ^ i : 포함
2. 추가
- '|' 사용
- 집합 S에 i 추가 : S | (1 << i)
3. 삭제
- '&', '~' 사용
- 집합 S에 i 삭제 : S & ~(1 << i)
4. 토글
- '^' 사용
- 집합 S에 i 토글 : S ^ (1 << i)
728x90
'Algorithm > 알고리즘 설명' 카테고리의 다른 글
| [알고리즘] 플로이드 와샬 (Floyd-Warshall) 알고리즘 (0) | 2020.10.03 |
|---|---|
| [알고리즘] 다익스트라 (Dijkstra) 알고리즘 (0) | 2020.10.02 |
| [알고리즘] 정렬 (Sort) (0) | 2020.09.17 |
| [알고리즘] 위상 정렬 (Topological Sorting) (0) | 2020.09.17 |
| [알고리즘] 이분 탐색 (Binary Search) (0) | 2020.08.31 |
댓글