Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 비트마스킹과 동적 프로그래밍 완벽 가이드

이 글에서는 비트마스킹과 동적 프로그래밍(Dynamic Programming)의 기본 개념을 먼저 학습한 뒤, 실제 문제를 함께 풀어보며 구현 과정에서 생길 수 있는 궁금증을 해결해 보겠습니다.

비트마스크(Bitmask)란?

비트마스크는 마스크(mask)라고도 불리며, 집합의 부분집합을 인코딩하는 N비트 시퀀스입니다. 마스크의 각 비트는 설정(set, 1)되거나 설정되지 않은(unset, 0) 상태를 가질 수 있으며, 이는 해당 요소가 부분집합에 포함되어 있는지 여부를 나타냅니다.

예를 들어, 마스크의 i번째 비트가 1로 설정되어 있다면 i번째 요소가 현재 부분집합에 존재한다는 의미입니다. N개의 요소를 가진 집합에는 각각 하나의 부분집합에 대응하는 2N개의 마스크가 존재할 수 있습니다.

문제를 해결할 때는 특정 마스크(즉, 하나의 부분집합)에서 시작해 값을 할당하고, 이전 마스크의 값을 활용하여 다음 마스크들의 값을 차례로 계산해 나갑니다. 이 과정을 반복하면 최종적으로 전체 집합에 대한 답을 구할 수 있습니다.

특정 마스크에 대한 최적해를 계산하려면, 해당 마스크에서 요소를 제거할 수 있는 모든 경우를 고려하고, 각 경우의 값들을 계산하여 최종 해답에 반영합니다.

동적 프로그래밍(Dynamic Programming)

동적 프로그래밍은 하위 문제(subproblem)를 해결하고 그 결과를 저장해 두었다가, 겹치는 다른 하위 문제를 풀 때 재활용하는 최적화 기법입니다. 같은 계산을 반복하지 않으므로 전체 실행 시간을 크게 단축할 수 있습니다.

그럼 이제 비트마스킹과 동적 프로그래밍을 활용해 풀어볼 실제 문제를 살펴보겠습니다.

문제: 파티의 고유한 모자

1부터 50까지 번호가 매겨진 50개의 모자가 있습니다. N명의 사람들이 각자 이 모자 중 일부를 소유하고 있습니다. 어느 날 모두가 파티에 모자를 쓰고 참석하기로 했는데, 서로 겹치지 않는 유니크한 모습을 연출해야 합니다. 사람 수 n과 각 사람이 소유한 모자 번호 목록이 주어졌을 때, 모든 사람이 서로 다른 번호의 모자를 쓸 수 있는 경우의 수를 구하는 것이 과제입니다.

입력 형식

첫 번째 줄에는 사람 수 n이 주어지고, 다음 n줄에는 각 사람이 소유한 모자 번호들이 공백으로 구분되어 주어집니다.

입력 예시:

3
4 45 10
25
45 10

출력 예시:

4

설명:

가능한 조합은 (4, 25, 45), (4, 25, 10), (45, 25, 10), (10, 25, 45)의 네 가지입니다.

경우의 수가 매우 커질 수 있으므로, 결과는 1000000007로 나눈 나머지 형태로 출력해야 합니다.

접근 방법

가장 단순한 해법은 첫 번째 사람부터 시작해 나머지 사람들에 대해 재귀적으로 모든 가능한 모자 조합을 탐색하는 것입니다. 하지만 이 방법은 중복 계산이 많아 최적화되어 있지 않습니다.

더 나은 해법은 비트마스킹과 DP를 결합하는 것입니다. 10명의 사람에 대해 크기 210(=1024)의 마스크를 만들고, 모자 번호별 소유자 정보를 저장하는 크기 51짜리 벡터를 생성한 뒤, 메모이제이션을 적용해 재귀적으로 경우의 수를 계산합니다. 이 방법의 시간 복잡도는 O(N × 2N)으로, 완전 탐색에 비해 훨씬 효율적입니다.

구현 예제

솔루션 구현 코드:

#include<bits/stdc++.h>
using namespace std;
vector<int> caps[101];
int dp[1025][101];
int allmask;
long long int uniqueCaps(int mask, int i) {
    if (mask == allmask) return 1;
    if (i > 100) return 0;
    if (dp[mask][i] != -1) return dp[mask][i];
    long long int ways = uniqueCaps(mask, i+1);
    int size = caps[i].size();
    for (int j = 0; j < size; j++) {
        if (mask & (1 << caps[i][j])) continue;
        else ways += uniqueCaps(mask | (1 << caps[i][j]), i+1);
        ways %= (1000000007);
    }
    return dp[mask][i] = ways;
}
int main() {
    int n = 3;
    // 1번 사람의 모자 컬렉션
    caps[4].push_back(0);
    caps[45].push_back(0);
    caps[10].push_back(0);
    // 2번 사람의 모자 컬렉션
    caps[25].push_back(1);
    // 3번 사람의 모자 컬렉션
    caps[45].push_back(2);
    caps[10].push_back(2);
    allmask = (1 << n) - 1;
    memset(dp, -1, sizeof dp);
    cout<<"파티에서 모두가 고유한 모자를 쓸 수 있는 경우의 수:\t"<<uniqueCaps(0, 1);
    return 0;
}

실행 결과

파티에서 모두가 고유한 모자를 쓸 수 있는 경우의 수: 4