비트마스킹

1. 개요 안녕하세요. 이 문제의 유형은 비트마스킹 + 그리디입니다. 저는 그리디만을 사용해서 풀이했습니다. 납득이 되는 풀이는 사실 비트마스킹을 사용하는 방법인데요. 저는 빙빙 돌아서 그리디만 사용했습니다. 2. 문제풀이 N개의 물병과 한 번에 들 수 있는 물병의 개수 K가 주어집니다. 물병을 합치는 로직은 결국 이진수의 원리와 같습니다. 물병 안에 차있는 물은 항상 2의 거듭제곱만큼만 채울 수 있죠. 저는 K - 1번의 루프를 통해 N보다 작거나 같은 2의 거듭제곱 중 가장 큰 수를 골라 N에서 빼주었습니다. 이는 K - 1개의 물통에 채울 물을 결정하는 로직입니다. 남은 물의 양 X가 2의 거듭제곱이거나 0이면 상점에서 물을 구매할 필요가 없고, 2의 거듭제곱이 아니라면 남은 물의 양보다 큰 2..

1. 문제풀이길이가 4인 임의의 비트필드 1xxx가 있다고 가정합시다. 이 비트필드에 xxx는 이전에 등장하였던 1xx, 1x, 1의 패턴이 동일하게 나타납니다. 즉 이전 결과 1xx, 1x, 1에서 등장하는 1의 개수를 알고 있다면 1xxx에서의 1의 개수를 알 수 있습니다. 이를 바탕으로 누적합 배열을 저장합니다.  다음엔 임의의 숫자 x에 대해서 1부터 x까지의 비트필드에서 등장하는 1의 개수를 누적합을 이용하여 계산해야합니다. 숫자 x의 비트필드를 1xxxx라고 한다면 우리는 1xxxx - 10000으로 최상위 비트 1이 몇 개까지 등장했는지 알 수 있습니다. 그 이전에 등장하는 1의 개수는 이전에 구한 누적합으로 계산이 가능합니다. 이런 방법으로 최상위 비트에서 순차적으로 내려오면 1부터 x까지..

1. 문제 풀이 비트마스킹을 활용한 다이나믹 프로그래밍을 사용하여 풀이하였습니다. dp 테이블은 다음과 같이 정의하였습니다. dp[i][j][k] : i자릿 숫자에서 마지막 자리의 숫자가 j이고 사용한 숫자가 1, 사용 안 한 숫자가 0인 비트필드 k 모든 계단 수를 구해주어야하는데 사용한 숫자 리스트에 대한 비트필드 k를 두어서 다이나믹 프로그래밍을 진행했습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector v..

1. 문제 풀이1-1. 문제 개요 안녕하세요. 오늘 풀어볼 문제는 백준 14391번 종이 조각입니다. 문제의 유형은 비트마스킹을 활용한 브루트포스 알고리즘 응용문제였습니다. 브루트포스 알고리즘인 만큼 백트래킹을 사용하셔도 되고 여러 가지 구현을 사용하든 풀이가 가능합니다. 저는 비트마스킹이 익숙지 않기 때문에 공부해 볼 겸 비트마스킹을 사용해서 풀이했습니다. 1-2. 종이를 어떻게 자를지 선택하는 방법 종이를 자르는 방법이 바로 이 문제의 핵심입니다. 종이를 자르는 방법은 가로와 세로 두 가지 경우밖에 없습니다. 종이의 크기는 N*M이고 각 칸을 가로로 자를지 세로로 자를지 결정하는 경우의 수는 2^(N*M)입니다.  종이를 자르는 방법은 두 가지이므로 비트의 단위로 분석을 해보겠습니다. 임의의 칸을 가..

1. 문제 풀이1-1. 문제 개요 안녕하세요. 오늘 풀어볼 문제는 백준 2234번 성곽입니다. 문제의 유형은 벽이 있는 2차원 배열에서 각 영역의 넓이를 구하는 flood fill 알고리즘의 응용이었습니다. flood fill의 경우 너비 우선 탐색과 깊이 우선 탐색 중 더 선호하시는 걸 선택하셔도 무방합니다. 저는 너비 우선 탐색을 선택해서 문제를 풀이했습니다.  이 문제는 여러 응용이 필요한 문제이기 때문에 너비 우선 탐색 기법을 사용한 flood fill 알고리즘에 대해서 어느 정도 기초가 필요합니다. 만약 이에 대해서 모르신다면 공부를 하고 기초 문제들을 몇 개 푼 뒤에 시도하는 것을 추천합니다. 1-2. 어느 방향이 벽인지 판별하는 방법 문제에서 주어진 2차원 배열에서 각 칸에는 0부터 15까지..