드디어 길고 긴 plzrun님의 문제셋이 끝났다. 이제 종만북에 들어갈 수 있다. (참고 글 : plzrun님의 알고리즘 문제풀이(PS) 시작하기) 앞으로 종만북을 공부하면서 배운 내용을 매주 정리할 생각이다. 아, 그리고 2권부터 볼거다. 첫 번째 주제는 비트마스크!
BOJ 11723 : 집합
비트마스크의 기본 연산들을 연습해볼 수 있는 문제.
11723번: 집합
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
www.acmicpc.net
#include <iostream>
using namespace std;
int main(void)
{
int n;
int set;
std::string cmd;
int arg;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
set = 0;
while (n--) {
cin >> cmd;
if (cmd.compare("add") == 0) {
cin >> arg;
set |= (1 << (arg - 1));
} else if (cmd.compare("remove") == 0) {
cin >> arg;
set &= ~(1 << (arg - 1));
} else if (cmd.compare("check") == 0) {
cin >> arg;
int check = set & (1 << (arg - 1));
if (check)
cout << 1 << '\n';
else
cout << 0 << '\n';
} else if (cmd.compare("toggle") == 0) {
cin >> arg;
set ^= (1 << (arg - 1));
} else if (cmd.compare("all") == 0) {
set = (1 << 21) - 1;
} else if (cmd.compare("empty") == 0) {
set = 0;
}
}
return 0;
}BOJ 1182 부분수열의 합
원래 재귀함수로 풀던걸, 모든 수열의 부분집합을 비트마스크로 표현하여 풀 수 있다.
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
#include <iostream>
using namespace std;
int arr[20];
int main(void)
{
int n, s, ans;
cin >> n >> s;
for (int i = 0; i < n; i++)
cin >> arr[i];
ans = 0;
for (int subset = 1; subset < (1 << n); subset++) {
int sum = 0;
for (int elem = 0; elem < n; elem++) {
/* if element is in the set */
if (subset & (1 << elem)) {
sum += arr[elem];
}
}
if (sum == s)
ans++;
}
cout << ans << endl;
return 0;
}
BOJ 18119 단어암기
집합 문제랑 똑같은 문제
18119번: 단어 암기
준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주
www.acmicpc.net
#include <iostream>
#include <string>
using namespace std;
int N, M;
string words[10001];
int query[10001];
int solve(int flag) {
int ans = 0;
for (int i = 0; i < N; i++) {
if ((query[i] & flag) == query[i])
ans++;
}
return ans;
}
void forget(int *flag, char c) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
return ;
else
(*flag) = (*flag) & ~(1 << (c-'a'));
}
void remember(int *flag, char c) {
*flag = *flag | (1 << (c-'a'));
}
int main(void)
{
int flag = ~0;
cin >> N >> M;
cin.tie(NULL);
ios_base::sync_with_stdio(false);
for (int i = 0; i < N; i++) {
cin >> words[i];
for (int j = 0; j < words[i].size(); j++) {
query[i] |= (1 << (words[i][j] - 'a'));
}
}
for (int i = 0; i < M; i++) {
int cmd;
char c;
cin >> cmd;
cin >> c;
if (cmd == 1) {
forget(&flag, c);
} else if (cmd == 2) {
remember(&flag, c);
}
cout << solve(flag) << '\n';
}
return 0;
}
BOJ 1194 달이 차오르자 가자
좀 신박했다. BFS에서 어떤 상태를 나타내는 queue를 만드는 유형의 문제가 있는데, 상태가 단일 값이 아니라 어떤 열쇠를 먹었나? 라는 비트마스크로 표현된다.
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,
www.acmicpc.net
#include <iostream>
#include <string>
#include <queue>
using namespace std;
// y, x, key
bool visited[51][51][1000];
string map[51];
int N, M;
// c = a, b, c, d, e, f
int addKey(int oldKey, char c) {
return oldKey | (1 << (c - 'a'));
}
// c = A, B, C, D, E, F
bool hasKey(int key, char c) {
return key & (1 << (c - 'A'));
}
int bfs(int sx, int sy) {
queue<int> qx, qy, qkey, qmove;
qx.push(sx); qy.push(sy); qkey.push(0); qmove.push(0);
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};
while (!qx.empty()) {
int x, y, key, move;
x = qx.front(); qx.pop();
y = qy.front(); qy.pop();
key = qkey.front(); qkey.pop();
move = qmove.front(); qmove.pop();
if (map[y][x] == '1')
return move;
char c;
for (int i = 0; i < 4; i++) {
int nx = dx[i] + x;
int ny = dy[i] + y;
if (0 <= nx && nx < M && 0 <= ny && ny < N &&
(c = map[ny][nx]) != '#' && !visited[ny][nx][key]) {
if ('a' <= c && c <= 'f') {
qx.push(nx);
qy.push(ny);
qkey.push(addKey(key, c));
visited[ny][nx][addKey(key, c)] = true;
} else if ('A' <= c && c <= 'F') {
if (!hasKey(key, c))
continue;
qx.push(nx);
qy.push(ny);
qkey.push(key);
visited[ny][nx][key] = true;
} else {
qx.push(nx);
qy.push(ny);
qkey.push(key);
visited[ny][nx][key] = true;
}
qmove.push(move + 1);
}
}
}
return -1;
}
int main(void)
{
cin >> N >> M;
int start_x, start_y;
for (int i = 0; i < N; i++) {
cin >> map[i];
for (int j = 0; j < M; j++) {
if (map[i][j] == '0') {
start_y = i;
start_x = j;
}
}
}
cout << bfs(start_x, start_y) << endl;
return 0;
}
BOJ 2098 외판원 순회
자 여기부터 내 능력 부족이다. 비트마스크는 그 자체로는 별로 어렵지 않은데, DP, 그래프랑 섞이다 보니까 난이도가 한도끝도 없이 올라간다. 이 문제는 아래 글의 아이디어를 참고하고 풀었다.
주요 아이디어는
- 어차피 모든 도시를 방문할거면, 출발지가 상관없다. 그리고 모든 도시를 방문하는 비용은 같다.
- 방문한 도시들과 현재 도시가 같다면, 중복되는 부분문제이므로 DP로 풀 수 있다.
2098번: 외판원 순회
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j
www.acmicpc.net
외판원 순회(TSP: Traveling Salesperson Problem)
외판원 순회(TSP: Traveling Salesperson Problem)란 도시들이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을
withhamit.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int cost_matrix[20][20];
int dp[20][100000];
const int INF = 100000000;
// current_city, visited_mask
int N;
int solve(int start_city, int current_city, int mask) {
// memoization
if (dp[current_city][mask] != INF) {
return dp[current_city][mask];
}
// visited all cities
if (mask == (1 << N) - 1) {
return (cost_matrix[current_city][start_city] > 0)
? cost_matrix[current_city][start_city] : INF;
}
for (int next_city = 0; next_city < N; next_city++) {
/* not visited , and can visit*/
if (!(mask & (1 << next_city)) &&
cost_matrix[current_city][next_city] > 0) {
int new_mask = mask | (1 << next_city);
// cost left to visit all cities
dp[current_city][mask] = min(dp[current_city][mask],
solve(start_city, next_city, new_mask)
+ cost_matrix[current_city][next_city]);
}
}
return dp[current_city][mask];
}
int main(void)
{
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> cost_matrix[i][j];
}
}
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 100000; j++) {
dp[i][j] = INF;
}
}
cout << solve(0, 0, 1 << 0) << endl;
return 0;
}
BOJ 1562 계단수
유명한 문제 중에 '쉬운 계단 수'라는 문제가 있는데, 드디어 쉽지 않은 계단 수를 만났다. 근데 그렇게 어렵진 않다. 원래 계단 수 문제는 DP[끝나는 숫자][길이] 로 풀었다면, DP[끝나는 숫자][길이][비트마스크(0-9까지 사용된 숫자들)]로 풀면된다.
1562번: 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
#include <iostream>
#include <vector>
using namespace std;
// digit, len, mask
int dp[10][101][1 << 10];
int main(void)
{
int N;
cin >> N;
const int b = 1000000000;
for (int i = 1; i < 10; i++) {
dp[i][1][1 << i] = 1;
}
for (int len = 2; len <= N; len++) {
for (int digit = 0; digit < 10; digit++) {
for (int mask = 0; mask < (1 << 10); mask++) {
int new_mask = mask | 1 << digit;
int sum;
if (digit == 0) {
sum = dp[digit + 1][len - 1][mask];
} else if (digit == 9) {
sum = dp[digit - 1][len - 1][mask];
} else {
sum = dp[digit - 1][len - 1][mask] % b;
sum += dp[digit + 1][len - 1][mask] % b;
sum %= b;
}
dp[digit][len][new_mask] += sum;
dp[digit][len][new_mask] %= b;
}
}
}
long long sum = 0;
for (int i = 0; i < 10; i++) {
sum += (dp[i][N][(1 << 10) - 1] % b);
sum %= b;
}
cout << sum << endl;
return 0;
}
문제집 만들어놓고 아직 못 푼 문제가 어마어마하다. 일단 비트마스크는 여기까지만 풀어야겠다. 아래 플레 문제들은 아직 풀 능력이 없다. 일단 백준 DP 강의부터 쭉 듣고, 문제 더 풀고 다시 와야겠다.
댓글