비트연산
logical right shift
arithmetic right shift
- 부호를 염두해두고 하는 shift 연산자
① getBit
bit연산자를 이용해 숫자 9의 이진수 값에서, i=(3)번 인덱스 값을 가져오려면?
9의 경우 3번 인덱스의 값이 1이다. (01001)
20의 경우 3번 인덱스의 값이 0이다 (10100)
우리가 원하는건 해당 자리수의 값이므로,
나머지 자리들은 다 0으로 만들어주고 해당 자리수만 원본데이터에서 가져오는 값을 만들어줘야 한다.
그렇게 구하기 위해서는 해당 인덱스의 값을 1로 세팅하고 나머지는 0으로 세팅하여 -> 1000
& 연산자를 해주면 원하는 값을 얻을 수 있다. = X
그러면 연산할 값인 1000은 어떻게 만들어낼까?
1을 i만큼 왼쪽으로 shift하면 1000 을 만들어낼 수 있다.
다음과 같이 해당 index값만 1이고 나머지는 0인 수를 만들어낼 수 있다.
9의 이진수 1001과 1000을 & 해준다.
주어진 값이 5인 경우는 이진수가 0101 이다.
-> 3번 index의 bit값이 0
연산 결과값 0000
결과가 0일때는 false, 0이 아닐때는 true를 반환하면
해당 index의 bit값이 0인지 1인지를 알아내는 함수를 만들 수 있다.
public class Test {
static boolean getBit(int num, int i) {
// 해당 index의 bit가 1이면 true, 0이면 false를 반환
return (num & (1<<i)) != 0;
}
public static void main(String[] args) {
// 1 0 0 1
System.out.println(getBit(9,3));
// 0 1 0 1
System.out.println(getBit(5,3));
}
}
결과값
② setBit
원하는 index에 1로 값을 세팅하려면?
1을 i만큼 왼쪽으로 shift 해서 1000 을 만들어낸다.
이것을 본래의 수 9 ( 1001 ) 과 | (or) 연산을 시킨다.
public class Test {
static int setBit(int num, int i) {
// 해당 index의 bit가 1이면 true, 0이면 false를 반환
return num | (1<<i);
}
public static void main(String[] args) {
// 숫자 5에 3번째 index를 1로 세팅해보자
// 0 1 0 1 -> 1 1 0 1 로
System.out.println(setBit(5,3));
}
}
결과로 13이 나온다.
③ clearBit
해당 index를 무조건 0으로 세팅하려면?
해당 index만 0이고 나머지 숫자들은 1인 0 1 1 1 과 &연산자를 해주면 된다.
-> 0 1 1 1 은 어떻게 만들까?
먼저 left shift를 통해 1 0 0 0 을 만들고
앞에 not을 붙여 bit를 정 반대로 바꿔준다.
0 1 1 1 = ~ 1 0 0 0
-> 그 다음 이걸 원본값과 & 연산자 해주면 해당 bit가 clear된다.
public class Test {
static int clearBit(int num, int i) {
return num & ~(1<<i);
}
public static void main(String[] args) {
// 1 0 0 1 -> 0 0 0 1
System.out.println(clearBit(9,3));
}
}
결과값 : 1
백준 1648. 격자판 채우기
문제
세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노를 이용해서 빈 공간이 없도록 채우는 방법의 수는 몇일까? 아래 그림은 N = 3, M = 6인 예이다.
입력
첫째 줄에 격자판의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 14)
출력
첫째 줄에 주어진 격자판을 2x1크기의 도미노로 빈 공간이 없도록 채우는 방법의 수를 9901로 나눈 나머지를 출력한다.
칸에 1을 넣어 넣었다는 표시를 해준다.
#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 14;
const int MOD = 9901;
int N, M;
int D[MAX*MAX][1 << MAX];
// D[i][bit] : i-1 번 타일까지 채워져있고, i번으로부터 M개의 타일의 상태가 bit인 경우의 수
// ex. D[7][5] : 7번째 칸부터 M개의 칸이 상태가 5이다. ( 5 = 0 0 0 1 0 1 (2) )
int tiling(int i, int bit) {
//전부 채워졌다면 결과에 1을 더해준다.
if (i == N * M && bit == 0)
return 1;
//마지막 칸까지 갔는데 다 채워지지 않은 경우 실패니깐 0을 반환
if (i >= N * M)
return 0;
// D[i][bit] : i-1 번 타일까지 채워져있고,
// i번부터 M개의 타일의 상태가 bit인 경우의 수
int &result = D[i][bit];
if (result != -1)
return result;
result = 0;
// i번째가 이미 채워져 있어서 칸을 채울 수 없는 경우
// 다음 칸을 채워야 함
// bit를 오른쪽으로 한비트 쉬프트
if (bit & 1)
result = tiling(i + 1, (bit >> 1));
//해당 칸이 칠해져있지 않다면 채워야함
else {
//해당 칸은 현재 위치에서 항상 좌상단이라고 가정하고 푼다
//2 * 1
result = tiling(i + 1, (bit >> 1) | (1 << (M - 1)));
//1 * 2
//M - 1번째 타일에 위치하지 않았고 (이럴 경우 1 * 2를 놓을 수 없으니깐)
//다음칸도 비어있을 경우
if ((i % M) != (M - 1) && (bit & 2) == 0)
result += tiling(i + 2, bit >> 2);
}
return result %= MOD;
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M; // N x M 칸
memset(D, -1, sizeof(D));
cout << tiling(0, 0) << "\n";
return 0;
}
출처
https://www.youtube.com/watch?v=yHBYeguDR0A&t=744s
https://jaimemin.tistory.com/1123
'알고리즘' 카테고리의 다른 글
[개념] 유클리드기하학,택시기하학 / Boj 3053. 택시 기하학 (0) | 2020.01.28 |
---|---|
[개념] 플로이드 와샬 (Floyd Warshall) / 백준 11404 (0) | 2020.01.27 |
[개념] 에라토스테네스의 체 (0) | 2020.01.17 |
[개념] 조합, 순열 + DFS,BFS (1) | 2020.01.16 |
[개념] 그래프 이론 (0) | 2020.01.15 |