비트 마스크
; 비트를 활용한 테크닉
- and(&), or(|), xor(^), not(~), shift(>>,<<)
왜 사용하는가 ?
- DP, 순열 등 배열 활용만으로 해결할 수 없는 문제에 사용
- 작은 메모리와 빠른 수행시간으로 해결 가능 but 원소의 수 많으면 안됨
- 집합을 배열의 인덱스로 표현 가능
활용
1. 삽입
BIT의 i번째 비트 값을 1로 변경 ; BIT | 1<<i
2. 삭제
BIT의 i번째 비트 값을 0으로 변경 ; BIT & ~1<<i
3. 조회
BIT의 i번째 비트 값 반환 ; BIT & (1<<i)
연습문제
https://www.acmicpc.net/problem/12813
12813번: 이진수 연산
총 100,000 비트로 이루어진 이진수 A와 B가 주어진다. 이때, A & B, A | B, A ^ B, ~A, ~B를 한 값을 출력하는 프로그램을 작성하시오.
www.acmicpc.net
'알고리즘' 카테고리의 다른 글
| [알고리즘] 다익스트라 (0) | 2022.06.06 |
|---|---|
| [알고리즘] DP(Dynamic Programming) (0) | 2022.06.06 |
| [알고리즘] 선형 리스트(Stack, Queue, Deque) (0) | 2022.06.06 |
| [알고리즘] 해시 (0) | 2022.06.06 |
| [알고리즘] 해싱(자료구조 기말고사 공부 정리) (0) | 2022.05.30 |
| [알고리즘] 탐색 (0) | 2022.05.29 |
| [알고리즘] 그래프 (0) | 2022.05.22 |
| [알고리즘] 연결 리스트 (0) | 2022.05.21 |
비트 마스크
; 비트를 활용한 테크닉
- and(&), or(|), xor(^), not(~), shift(>>,<<)
왜 사용하는가 ?
- DP, 순열 등 배열 활용만으로 해결할 수 없는 문제에 사용
- 작은 메모리와 빠른 수행시간으로 해결 가능 but 원소의 수 많으면 안됨
- 집합을 배열의 인덱스로 표현 가능
활용
1. 삽입
BIT의 i번째 비트 값을 1로 변경 ; BIT | 1<<i
2. 삭제
BIT의 i번째 비트 값을 0으로 변경 ; BIT & ~1<<i
3. 조회
BIT의 i번째 비트 값 반환 ; BIT & (1<<i)
연습문제
https://www.acmicpc.net/problem/12813
12813번: 이진수 연산
총 100,000 비트로 이루어진 이진수 A와 B가 주어진다. 이때, A & B, A | B, A ^ B, ~A, ~B를 한 값을 출력하는 프로그램을 작성하시오.
www.acmicpc.net
'알고리즘' 카테고리의 다른 글
| [알고리즘] 다익스트라 (0) | 2022.06.06 |
|---|---|
| [알고리즘] DP(Dynamic Programming) (0) | 2022.06.06 |
| [알고리즘] 선형 리스트(Stack, Queue, Deque) (0) | 2022.06.06 |
| [알고리즘] 해시 (0) | 2022.06.06 |
| [알고리즘] 해싱(자료구조 기말고사 공부 정리) (0) | 2022.05.30 |
| [알고리즘] 탐색 (0) | 2022.05.29 |
| [알고리즘] 그래프 (0) | 2022.05.22 |
| [알고리즘] 연결 리스트 (0) | 2022.05.21 |
