[Algorithm/DP] 부분집합의 합 문제(브루트포스, 백트래킹, 메모이제이션, 타뷸레이션)

부분집합의 합 문제(브루트포스, 백트래킹, 메모이제이션, 타뷸레이션)

• 금전등록기에 남아 있는 동전을 조합하여 필요한 거스름돈을 만들 수 있는지 확인해보자.

• 필요한 잔돈이 73270원이고, 10000원권, 1000원권과 500원, 100원, 50원, 10원 동전들이 전체 100개가 들어있다면?

  • 가능한 모든 조합을 시도해보면서 거스름돈의 금액을 맞추는 것은 너무 복잡해지고 실제로 구현하는 것은 너무 복잡하고 비현실적

• 이러한 문제를 부분집합의 합 문제(subset sum problem)이라고 한다

"음수가 아닌 정수로 이루어진 집합 S와 임의의 정수 x가 주어질 때, S의 부분집합 중에서 그 원소의 합이 x와 같은 부분집합이 존재하는가?"

• ex) S = {13, 79, 45, 29}, x = 42 --> True

• 원소의 개수가 n인 집합 S의 전체 부분집합 개수는 2^n개임을 알 수 있다.

  • 이는 n이 증가함에 따라 부분집합의 개수가 기하 급수적으로 증가한다.

  • Brute Force로 모든 부분집합의 합을 일일히 구하는 시간 또한 기하 급수적으로 증가한다.

• 부분집합의 합 문제에 동적 계획법을 적용할 수 있는지 확인해보자

1단계: 동적 계획법 필요조건 분석하기

• 부분집합의 합과 같은 문제에 직면하면 먼저 이 문제를 DP로 해결할 수 있는지 확인해야 한다.

• 일반적으로 주어진 문제가 다음 속성을 가지고 있다면 DP로 해결할 수 있다.

  • 중복되는 부분 문제 : 일반 분할 정복 기법과 마찬가지로 퇴종해는 여러 개의 부분 문제 조합으로 표현될 수 있어야 한다.

    • 그러나 분할 정복과는 달리 특정 부분 문제가 여러 번 발생할 수 있다.

  • 최적 부분 구조 : 주어진 문제에 대해 최적해는 부분 문제의 최적해로부터 생성될 수 있다.

부분집합의 합 문제의 DP 필요조건 분석

• 크기가 n인 부분집합은 크기가 n - 1인 부분집합에 새로운 원소 하나를 추가하여 만들 수 있다.

  • 이는 새로운 부분집합을 구성하기 위한 최적의 방법이며, 크기가 0보다 큰 모든 부분집합에 적용된다.

  • 따라서 부분집합의 합 문제는 최적 부분 구조를 가진다고 할 수 있다.

• 또한 서로 다른 부분집합이 더 작은 크기의 같은 부분집합으로부터 생성될 수 있다.

  • ex) {13 79 45}와 {13 79 29}는 모두 더 작은 크기의 부분집합 {13 79}로 부터 생성된다.

  • 따라서 부분집합의 합 문제는 중복되는 부분 문제 속성도 가지고 있다.

• 두 가지 조건을 모두 만족하기 때문에 부분집합의 합 문제는 동적 계획법(DP)으로 해결할 수 있다.

2단계: 기저 조건과 상태 정의하기

• 이제 이 문제에서 상태(state)를 구성하기 위해 필요한 것이 무엇인지 파악해야 한다.

  • 즉, 각 부분 문제를 다른 부분 문제와 다르다고 판단할 수 있는 기준을 찾아야 한다.

• 처음부터 DP 상태를 제대로 정의하는게 쉽지 않을 수 있다. 따라서 가장 직관적인 방법부터 구현해보는 것도 좋다.

  • 여기서는 전수 조사, 백트래킹, 메모이제이션, 타뷸레이션 4가지 접근 방법을 고려하며 문제를 해결해보겠다.

  • 물론 여기서 처음 세 방법은 입력 크기가 증가함에 따라 한계가 금방 드러난다.

전수 조사(Bruete-Force)

• 전수 조사 방법은 분명히 비효율적이지만 현재 다루고 있는 문제를 제대로 이해하는데 도움이 된다.

  • 단순성 : 문제에 대한 이해 없이 복잡한 방법으로 접근하는 것 보다 최대한 단순하게 접근하는 것이 문제의 본질을 이해하기 쉽다

  • 정답 비교를 위한 수단

  • 부분 문제를 시각화하는 능력 : 올바른 해답이 형성되는 방식을 시각화하는 수단을 제공하여 다른 풀이에서 사용할 수 있는 필수 패턴을 찾을 수 있다.

전수 조사 방식으로 부분집합의 합 문제 풀기

• 헤더 파일 및 매크로 함수 정의

#include <iostream>
#include <vector>
#include <algorithm>

#define DEBUG 1

#if DEBUG
#define PRINT(x) cerr << x
#else
#define PRINT(x)
#endif

using namespace std;

• 부분집합 생성

  • 재귀 호출을 통해 집합의 모든 부분집합을 구하는 GetAllSubsets()함수를 정의한다.

  • 각 부분집합은 원소의 개수에 따라 allSubsets라는 3차원 벡터에 저장된다.

void GetAllSubsets(vector<int> set, vector<int> subset,
    int index, vector<vector<vector<int>>>& allSubsets)
{
    // 집합 set의 끝에 도달한 경우
    if (index == set.size())
    {
        // 부분집합 크기를 인덱스로 사용하여 부분집합을 allSubsets에 추가
        allSubsets[subset.size()].push_back(subset);
        return;
    }

    // 원소를 추가하지 않고 재귀 호출
    GetAllSubsets(set, subset, index + 1, allSubsets);

    // 원소를 부분집합에 추가한 후 재귀 호출
    subset.push_back(set[index]);
    GetAllSubsets(set, subset, index + 1, allSubsets);
}

• 부분집합의 합 계산 및 비교

  • SubsetSum_BruteForce 함수는 GetAllSubsets 함수를 호출하여 모든 부분집합을 생성한 후, 각 부분집합의 합이 목표 값(target)과 같은지 확인합니다.

    • 목표 값과 일치하는 부분집합이 발견되면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

bool SubsetSum_BruteForce(vector<int> set, int target)
{
    vector<vector<vector<int>>> allSubsets(set.size() + 1);

    GetAllSubsets(set, {}, 0, allSubsets);

    for (int size = 0; size <= set.size(); size++)
    {
        PRINT("부분집합의 원소 개수: " << size << endl);

        for (auto subset : allSubsets[size])
        {
            PRINT("\t{ ");

            int sum = 0;
            for (auto number : subset)
            {
                sum += number;
                PRINT(number << " ");
            }

            PRINT("} = " << sum << endl);

            if (sum == target)
                return true;
        }
    }

    return false;
}

• 메인 함수

int main()
{
    vector<int> set = {13, 79, 45, 29};
    int target = 58;

    bool found = SubsetSum_BruteForce(set, target);

    if (found)
    {
        cout << "원소 합이 " << target << "인 부분집합이 있습니다." << endl;
    }
    else
    {
        cout << "원소 합이 " << target << "인 부분집합이 없습니다." << endl;
    }
}

최적화 적용하기 - 백트래킹(backtracking)

• 전수 조사 방식은 성능 면에서 가장 비효율적이기 때문에 사용하기 마땅치 않다.

  • 더 이상 해답이 나올 수 없는 경우에 대해서도 모든 조사를 수행해야 한다.

• 모든 부분 문제 중에서 유효하지 않은 모든 경우를 제거하는 백트래킹(bactracking) 기법을 사용할 수 있다.

• 백트래킹 방법을 구현하려면 주어진 문제의 기저 조건과 상태의 재귀적 표현을 결정해야 한다.

• ex) factorial 계산 함수

#include <bits/stdc++.h>
using namespace std;

int Factorial(int n) {
    // 기저 조건 - 재귀 호출 멈추기
    if (n == 1) return 1;
    return n * Factorial(n - 1);
}

• 부분집합의 합 문제에서는 다음과 같이 기저 조건을 정의할 수 있다.

만약 현재 부분집합의 합이 target과 같다면: TRUE
그렇지 않다면:
    - 만약 현재 부분집합의 합이 target보다 크면: FALSE
    - 만약 집합의 끝에 도달한 경우: FALSE

• 기조 조건을 만들었으니 상태 변화 방법을 정의해야 한다.

  • 크기가 2인 부분집합을 만들 때, 크기가 1인 집합을 선택하고 이 부분 집합이 가지고 있는 원소의 인덱스보다 큰 인덱스의 원소를 원본 집합에서 하나씩 골라 추가한다.

  • 매번 부분집합의 합을 계산하지만, 목표치보다 큰 경우에는 동작을 중지한다는 점에서 brute force 방식과 차이점이 있다.

• 따라서 상태 변화 방식을 다음과 같이 정의할 수 있다.

집합 set의 i번째 원소 set[i]와 부분집합 ss에 대해:

    만약 ss의 합에 set[i]를 더한 결과가 target보다 작거나 같으면:

        1) ss에 set[i]를 추가
        2) i를 증가

        다음 상태 -> (i += 1, ss = ss U set[i])

    모든 경우에 대해:

        1) ss에 set[i]를 추가하지 않음
        2) i 증가

        다음 상태 -> (i += 1, ss = ss)

• 이 문제는 주어진 집합의 부분집합 중에서 그 합이 정수 target과 같은 부분집합이 있는지 판별하는 것이 목적이다.

  • 실제 부분집합이 어떻게 구성되는지 나타낼 필요가 없고, 단지 그 부분집합의 합만 검사하면 된다.

• 따라서 다음과 같이 상태 변화 의사 코드를 간결하게 변경할 수 있다.

집합 set의 i번째 원소 set[i]와 부분집합의 합 sum에 대해:

    만약 sum에 set[i]를 더한 결과가 target보다 작거나 같으면:

        1) sum에 set[i]를 더함
        2) i를 증가

        다음 상태 -> (i += 1, sum += set[i])

    모든 경우에 대해:

        1) sum에 set[i]를 더하지 않음
        2) i 증가

        다음 상태 -> (i += 1, sum = sum)

• 중간 단계 상태를 sum과 i 두 개의 정수로 표현할 수 있다.

• 더 개선할 방법

  • target 값부터 시작해서 매 단계마다 set[i]를 빼는 형태로 전환하면 target 값을 가지고 다닐 필요가 없다.

  • 함수 호출 전체 집합을 정렬함으로써 target보다 값이 커지는 경우를 만나면 나머지 집합 원소는 고려하지 않도록 만들 수도 있다.

백트래킹을 사용하여 부분집합의 합 문제 풀기

• 백트래킹 방식으로 부분집합의 합 문제를 푸는 함수

bool SubsetSum_Backtracking(vector<int> set, int sum, int i)
{
    // 만약 현재 부분집합의 합이 target과 같다면
    if (sum == 0)
    {
        return true;
    }

    // 만약 현재 부분집합의 합이 target보다 크거나, 집합의 끝에 도달했다면
    if (i == set.size() || set[i] > sum)
    {
        return false;
    }

    // Case 1: sum에서 set[i]을 빼서 재귀 호출 (i번째 원소를 부분집합에 추가)
    // Case 2: sum을 그대로 전달하여 재귀 호출 (i번째 원소를 부분집합에 추가하지 않음)

    return SubsetSum_Backtracking(set, sum - set[i], i + 1)
        || SubsetSum_Backtracking(set, sum, i + 1);
}

3단계: 메모이제이션

• 부분집합의 합 목표치가 매우 큰 경우 백트래킹 방법 또한 기저 조건을 늦게 만나기 때문에 소요 시간이 길다.

• 메모이제이션이라는 하향식 방법을 사용하기에 필요한 정보를 이미 가지고 있으므로 캐시 사용만 고려해 개선해주면 된다

캐시 사용하기

• 메모이제이션을 사용하는데 있어 가장 중요한 것은 캐시를 어떻게 사용할 것인지를 결정하는 것이다.

  • 방법 1: 정수 인덱스를 사용하는 일반 배열

    • 상태를 정수 인덱스로 나타내는 것이다.

    • map보다 빠르다. 맵은 주어진 키에 대한 위치를 찾는 작업이 필요하기 때문.

  • 방법 2: 프로그래밍 언어에서 제공하는 해시 기능을 사용하여 상태를 문자열로 표현한 해시 테이블 / 해시 맵

    • 상태를 정수 인덱스로 표현할 수 있다 하더라도 값이 너무 크다면 실제 필요한 메모리보다 훨씬 큰 크기의 배열을 만들어야 하기 때문에 비합리적일 수 잇다. 이 경우 맵을 사용하는 편이 나을 수 있다.

    • ex) c++의 std::unordered_map 사용

  • 방법 3: 자체적으로 생성한 해시 함수를 이용하여 상태를 표현한 해시 테이블 / 해시 맵

    • ex) c++의 std::map 사용

    • 기본적으로 키로 사용할 수 없는 자료형에 대해서는 프로그래머가 직접 해싱 함수를 만들어야 한다.

• 캐시 사용 방법은 다음을 만족해야 한다.

  • 유효성 : 캐시의 키 값은 서로 다른 상태에 대해 충돌이 발생하지 않도록 표현해야 된다.

    • ex) target : 8이고, 집합 원소의 합을 key(상태)로 사용할 때, {1 5 6 2 3 9}에서 {1 5}, {6}, {1 2 3}은 모두 Key가 6이다. 3번째의 경우 false를 반환한다. 하지만 {1 5}와 {6}은 2를 추가하여 8을 구성할 수 있으므로 false를 반환하면 안 된다

    • 특정 sum 값을 갖는 상태에서 목표치를 찾지 못한다는 것이 같은 sum값을 갖는 다른 상태에서도 목표치를 찾지 못한다고 잘못 인식할 수 있다는 것이다.

  • 유용성 : 캐시에 저장된 값을 참조하는 경우가 아예 발생하지 않는다면 아무 의미가 없다.

    • ex) 부분집합 구성에 사용된 원소의 모든 인덱스를 키로 사용하면 모든 상태가 고유한 키로 구성되어, 같은 부분 문제에 의해 캐시가 참조되는 경우가 발생하지 않는다.

메모이제이션을 이용하여 부분집합의 합 문제 풀기

bool SubsetSum_Memoization(vector<int>& set, int sum, int i,
    vector<vector<int>>& memo)
{
    // 만약 현재 부분집합의 합이 target과 같다면
    if (sum == 0)
    {
        return true;
    }

    // 만약 현재 부분집합의 합이 target보다 크거나, 집합의 끝에 도달했다면
    if (i == set.size() || set[i] > sum)
    {
        return false;
    }

    // 현재 상태가 캐시에 있는지 확인
    if (memo[i][sum] == UNKNOWN)
    {
        // 현재 상태에 대한 솔루션을 구하여 캐시에 저장
        bool append = SubsetSum_Memoization(set, sum - set[i], i + 1, memo);
        bool ignore = SubsetSum_Memoization(set, sum, i + 1, memo);

        memo[i][sum] = append || ignore;
    }

    // 캐시에 저장된 값을 반환
    return memo[i][sum];
}

4단계: 타뷸레이션

• 주어진 집합에 대해 가능한 모든 부분 집합의 합 목록을 얻고 싶다고 가정해보자.

  • 1~3단계 방법으로는 각각의 부분집합의 합을 구하기 위해 알고리즘을 반복적으로 실행해야 한다.

    • 이러한 경우에는 타뷸레이션(tabulation) 방법이 효과적이다.

• 표를 사용하는 형태의 해법을 구현하는 것을 개념화하기 쉽지 않다.

  • 표 형식 해법은 복잡한 계층을 for/while 문법에 의한 단순한 반복문 구조로 표현해야 한다

• 메모이제이션과 마찬가지로 먼저 기저 조건과 상태를 정의한다.

• 그리고 서로 다른 상태에 대한 해법을 어떻게 저장할 것인지 결정해야 한다.

  • 타뷸레이션에서는 보통 간단한 배열 또는 벡터를 사용한다.

    • 피보나치, 팩토리얼 타뷸레이션 코드를 떠올려보자

• 피보나치 수열, 팩토리얼 문제와 부분집합의 합 문제의 근본적인 차이점은 상태 표현을 위해 필요한 차원 수가 다르다는 점이다.

  • 부분집합의 합 문제에서는 현재까지의 부분집합 합과 현재 처리하고 있는 집합의 인덱스가 필요하다.

• 부분집합의 합 문제에서는

  • 크기가 k인 부분집합은 크기가 k - 1인 부분집합에 새로운 원소를 추가하여 구성할 수 있다.

  • 인덱스 i에서 같은 부분집합의 합 x를 갖는 어떤 부분집합의 조합이든 최종적으로 같은 결과를 형성한다.

    • for문을 돌려서 인덱스 i = 0부터 n - 1까지 순차적으로 돌리기 때문에 같은 인덱스에서 같은 부분집합 x를 구성하면 같은 결과를 형성한다

  • 즉, 어떤 방식으로 특정 상태까지 도달했는지 상관 없이 이 상태 이후의 결과는 모두 같게 나타난다.

하향식 로직을 상향식 로직으로 뒤집어 생각하기

1. 부분집합의 합과 인덱스를 0으로 설정하여 시작
2. 입력 집합 전체에 대해 반복
   1. 만약 인덱스가 0에서 i사이일 때 x와 같은 부분집합의 합을 찾을 수 있다면, 인덱스가 0에서 i + 1 사이에서도 x와 같은 부분집합의 합을 찾을 수 있다. (i + 1번째 원소를 부분집합에 포함하지 않는 경우)
   2. 만약 인덱스가 0에서 i사이일 때 x와 같은 부분집합의 합을 찾을 수 있다면, 인덱스가 0에서 i + 1 사이에서도 x + set[i]와 같은 부분집합의 합을 찾을 수 있다. (i + 1번째 원소를 부분집합에 포함하는 경우)

• 표 채우기 로직

만약 부분집합의 합이 x이고 인덱스가 i인 경우, 다음 중 하나라도 성립하면 DP(i, x) = true이다.

    - x가 set[i]보다 작고, DP(i - 1, x) = true

        : x가 set[i]보다 작다는 말은 set[i]를 포함하지 않는다는 말이다.

        : 이 경우, 이전 인덱스까지의 부분집합에서 이미 합 x를 만들 수 있었다면, 현재 인덱스에서도 합 x를 만들 수 있습니다

    - x가 set[i]보다 크거나 같고, DP(i - 1, sum) = true 또는 DP(i - 1, sum - set[i]) = true

        : x에 set[i]를 포함시키는 경우이다

        : 이전 인덱스까지의 부분집합에서 이미 합 sum을 만들 수 있다면, 현재 원소를 추가하지 않고도 합 sum을 만들 수 있습니다.

        : 이전 인덱스까지의 부분집합에서 합 sum - set[i]를 만들 수 있었다면, 현재 원소 set[i]를 추가하여 합 sum을 만들 수 있습니다.

그렇지 않으면 DP(i, x) = false

• 즉, 인덱스가 0에서 i 사이일 때 부분집합의 합이 x가 될 수 있다면 인덱스가 0에서 i + 1 사이일 때에는 부분집합의 합이 x 또는 x + set[i]가 될 수 있다.

타뷸레이션을 이용하여 부분집합의 합 문제 풀기

• dp의 첫 번째 차원 크기는 입력 집합의 크기와 같고, 두 번째 차원의 크기는 입력 집합의 모든 원소 합보다 1만큼 크게 설정한다.

• dp의 모든 원소는 false로 초기화하지만, 부분집합의 합이 0인 기저 조건에 대해서는 true로 설정한다.

vector<vector<bool>> SubsetSum_Tabulation(vector<int>& set)
{
    int maxSum = 0;

    for (int i = 0; i < set.size(); i++)
    {
        maxSum += set[i];
    }

    vector<vector<bool>> DP(set.size() + 1, vector<bool>(maxSum + 1, 0));

    for (int i = 0; i < set.size(); i++)
    {
        DP[i][0] = true;
    }

    for (int i = 1; i <= set.size(); i++)
    {
        for (int sum = 1; sum <= maxSum; sum++)
        {
            if (sum < set[i - 1])
            {
                DP[i][sum] = DP[i - 1][sum];
            }
            else
            {
                DP[i][sum] = DP[i - 1][sum]
                    || DP[i - 1][sum - set[i - 1]];
            }
        }
    }

    return DP;
}

• 테스트 코드

int main()
{
    vector<int> set = {16, 1058, 22, 13, 46, 55, 3, 92, 47, 7,
                       98, 367, 807, 106, 333, 85, 577, 9, 3059};
    int target = 6076;
    int tests = 4;

    sort(set.begin(), set.end());

    for (int i = 0; i < tests; i++)
    {
        bool found = false;

        clock_t timer = clock();

        switch (i)
        {
        case 0:
            found = SubsetSum_BruteForce(set, target);
            break;
        case 1:
            found = SubsetSum_Backtracking(set, target, 0);
            break;
        case 2:
        {
            // 메모이제이션 테이블 초기화
            vector<vector<int>> memo(set.size(), vector<int>(7000, UNKNOWN));

            found = SubsetSum_Memoization(set, target, 0, memo);
            break;
        }
        case 3:
        {
            int total = 0;
            for (auto number : set)
                total += number;

            vector<vector<bool>> DP = SubsetSum_Tabulation(set);
            found = DP[set.size()][target];

            vector<int> subsetSums;
            for (int sum = 1; sum <= total; sum++)
            {
                if (DP[set.size()][sum])
                {
                    subsetSums.push_back(sum);
                }
            }

            cout << "다음과 같이 " << subsetSums.size() << "가지의 부분집합의 합이 가능합니다:" << endl;

            for (auto sum : subsetSums)
                cout << sum << " ";
            cout << endl;

            break;
        }
        }

        if (found)
        {
            cout << "원소 합이 " << target << "인 부분집합이 있습니다." << endl;
        }
        else
        {
            cout << "원소 합이 " << target << "인 부분집합이 없습니다." << endl;
        }

        GetTime(timer, types[i]);
        cout << endl;
    }
}

• DP 테이블을 이용하여 모든 가능한 부분집합의 합을 알아낼 수 있다.

Ref) 코딩테스트를 위한 자료구조 + 알고리즘 with C++