본문 바로가기
종만북

비트마스크

by hygoni 2020. 12. 1.
※ 이 블로그의 글은 글쓴이가 공부하면서 정리하여 쓴 글입니다.
※ 최대한 내용을 검토하면서 글을 쓰지만 틀린 내용이 있을 수 있습니다.
※ 만약 틀린 부분이 있다면 댓글로 알려주세요.

드디어 길고 긴 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;
}

 

oh god...

 

 

문제집 만들어놓고 아직 못 푼 문제가 어마어마하다. 일단 비트마스크는 여기까지만 풀어야겠다. 아래 플레 문제들은 아직 풀 능력이 없다. 일단 백준 DP 강의부터 쭉 듣고, 문제 더 풀고 다시 와야겠다.

반응형

'종만북' 카테고리의 다른 글

비트마스크  (2) 2020.12.01

댓글2