Subset Sum 문제 풀이: 재귀, 비트마스크, DP

Subset Sum은 주어진 수들 중 일부를 골라 목표 합을 만들 수 있는지 판정하는 대표적인 조합 탐색 문제입니다.

이 글은 합이 0이 되는 부분집합을 찾는 예제로 재귀 탐색, 비트마스크 완전탐색, DP 방식의 차이를 정리합니다.

 

핵심 정리

Subset Sum 문제는 각 원소를 고를지 말지 결정하면서 가능한 합을 확인하는 문제입니다. 가장 직접적인 방법은 재귀로 현재 원소를 선택하는 경우와 선택하지 않는 경우를 모두 탐색하는 것입니다. 같은 생각을 비트마스크로 바꾸면 모든 부분집합을 반복문으로 순회할 수 있습니다. DP 방식은 지금까지 만들 수 있는 합을 저장해 두고 다음 원소를 더한 새 합을 갱신하는 방식이라, 숫자 범위가 적당할 때 완전탐색보다 빠르게 동작할 수 있습니다.

• 재귀 풀이는 각 원소마다 선택한다와 선택하지 않는다를 나누어 탐색합니다.
• 비트마스크 풀이는 부분집합 하나를 정수의 비트 패턴으로 표현합니다.
• 두 방식 모두 모든 부분집합을 보므로 원소 수가 커지면 빠르게 느려집니다.
• DP 풀이는 만들 수 있는 합의 집합을 저장하면서 다음 원소를 반영합니다.
• DP는 합의 가능한 범위가 너무 넓으면 메모리 사용량이 커질 수 있습니다.
• 문제 크기가 작으면 완전탐색이 단순하고, 합의 범위가 작으면 DP가 실용적입니다.

원문은 세 가지 풀이 코드를 한 번에 보여주는 구조였습니다. 이번 보강은 코드를 보기 전에 각 풀이가 어떤 선택 구조를 갖는지 먼저 이해하도록 순서를 잡았습니다.

이어서 볼 글

• 비트 연산과 비트마스크 기본 개념 - 부분집합을 비트마스크로 표현하는 데 필요한 기초 글이다.
• 조합 계산 개념: nCk 공식, 그룹 분할, DP 구현 - 부분집합 선택과 조합 계산이 함께 쓰이는 배경 글이다.
• LCS 최장 공통 부분 수열: DP 점화식과 풀이 - 다른 대표 DP 문제의 상태 정의와 점화식 흐름을 비교할 수 있다.

 

다음의 문제를 생각해보자.

배열이 하나 주어진다.

{3, -2, 5, 7, -3, 1}

이 때 이 배열의 일부 원소를 더해서 0이 되는 경우가 있는지 알아내는 프로그램을 작성한다고 해보자.

위 배열에 대한 답은 True이다 {-2, 5, -3}을 부분집합으로 취해 더하면 0을 만드는 것이 가능하기 때문이다.

subset sum 문제는 NP-complete 문제중 가장 단순한 형태로서, brute-force 이외에 P솔루션이 존재하지 않는다.

brute-force의 시간 복잡도는 모든 부분집합을 구해서 더해보는 것이기 때문에 $O(2^n)$이 된다.

다만, dynamic-programming을 쓸 경우, 반복계산을 cache하는 방법으로 수행속도를 빠르게 할 수 있으나 바로 그 cache한다는 속성 때문에 n의 범위가 커지면 메모리 초과로 쓸 수 없다.

오늘은 subset sum문제를 푸는 세 가지 방법을 검토해보자.

첫번째 방법은 재귀를 이용해서 푸는 방법이다.

bool go(vector<int>&v, int ix, int cur_sum, int count)
{
    if(ix==(int)v.size())
    {
        if(cur_sum==0&&count>0) return true;
        return false;
    }
    bool r1 = go(v, ix+1, cur_sum+v[ix], count+1);
    bool r2 = go(v, ix+1, cur_sum, count);
    return r1 || r2;
}

bool recursive(vector<int>& v)
{
    return go(v, 0, 0, 0);
}

두번째 방법은 binary operation을 사용해 재귀없이 loop 로 푸는 방법이다.

bool naive(vector<int>& v)
{
    int n = (int)v.size();
    for(int i=1;i<(1<<n);i++)
    {
        int s = 0;
        for(int j=0;j<n;j++) if((1<<j)&i) s+=v[j];
        if(s==0) return true;
    }
    return false;
}

위 두 가지방법은 시간 복잡도가 $O(2^n)$이기 때문에 n이 20만 넘어도 너무 느려져서 쓸 수 없게 된다.

다음 세번째 방법은 dynamic programming(이하 dp)을 사용해서 푸는 방법이다.

bool dp(vector<int>& v)
{
    map<int, bool> m, m2;
    for(int i=0;i<(int)v.size();i++)
    {
        m2 = m;
        for(auto it=m.begin();it!=m.end();it++)
        {
            m2[it->first + v[i]] = true;
        }
        m2[v[i]] = true;
        m = m2;
    }
    if (m[0]) return true;
    return false;

}

위의 세번째 방법은 n의 범위가 너무 크지 않은 경우 상당히 빠른시간을 보장한다($O(n \times m)$)

m은 n의 범위(최대값)이 되겠다. 최대값이 작은 경우는 다항시간에 가까운 실행시간을 보장한다.

testcase를 포함한 전체 소스코드는 다음과 같다.