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

C++ 파티션 문제 완벽 가이드: 배열을 합이 같은 두 부분집합으로 나누는 방법

파티션 문제(Partition Problem)는 주어진 배열을 두 개의 부분집합으로 나눌 수 있는지, 그리고 나누어진 두 부분집합에 속한 원소들의 합이 정확히 같은지를 판단하는 문제입니다. 이 문제는 부분집합 합 문제(Subset Sum Problem)의 변형이며, 부분집합 합 문제는 다시 배낭 문제(Knapsack Problem)의 변형에 해당합니다. 조건이 충족되면 "Yes", 그렇지 않으면 "No"를 출력해야 합니다.

입력 예시

arr[] = {6, 4, 8, 12, 15}

위 배열의 전체 합은 6 + 4 + 8 + 12 + 15 = 45로 홀수입니다. 따라서 합이 같은 두 부분집합으로 나누는 것은 불가능합니다.

접근 방법 1: 재귀(완전 탐색)

가장 먼저 배열의 모든 원소의 합을 구합니다.

  • 총합이 홀수라면 두 집합으로 균등하게 나눌 수 없으므로 즉시 false를 반환합니다.
  • 총합이 짝수라면, 합이 sum/2인 부분집합이 존재하는지 탐색합니다.

주어진 배열의 각 원소를 하나씩 살펴보며 다음 두 가지 선택지를 재귀적으로 시도합니다.

  • 현재 원소를 부분집합에 포함하고, 나머지 원소들로 목표 합을 채웁니다.
  • 현재 원소를 부분집합에서 제외하고, 나머지 원소들로 같은 과정을 반복합니다.

포함하거나 제외하는 어느 한쪽이라도 성공하면 true를, 둘 다 실패하면 false를 반환합니다. 재귀 호출은 더 이상 탐색할 원소가 없거나 목표 합이 음수가 되면 종료되며, 목표 합이 0이 되면 해당 부분집합을 찾은 것이므로 true를 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
bool isSubsetSum(int arr[], int n, int sum) {
    if (sum == 0)
        return true;
    if (n == 0 && sum != 0)
        return false;
    if (arr[n - 1] > sum)
        return isSubsetSum(arr, n - 1, sum);
    return isSubsetSum(arr, n - 1, sum) ||
    isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}
bool findPartiion(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    if (sum % 2 != 0)
        return false;
    return isSubsetSum(arr, n, sum / 2);
}
int main() {
    int arr[] = {
        6,
        4,
        8,
        12,
        15
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (findPartiion(arr, n) == true)
        cout << "Is possible to divide into two subsets " "of equal sum";
    else
        cout << "Is impossible to divide into two subsets" " of equal sum";
    return 0;
}

실행 결과

Is impossible to divide into two subsets of equal sum

재귀 풀이는 모든 경우를 탐색하므로 시간 복잡도가 O(2n)으로, 배열의 크기가 커지면 매우 느려진다는 단점이 있습니다.

접근 방법 2: 동적 계획법(Dynamic Programming)

원소들의 총합이 지나치게 크지 않다면 동적 계획법으로 훨씬 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 크기가 (sum/2 + 1)인 1차원 불리언 배열 part[]를 생성하고, part[j]는 "지금까지 확인한 원소들만으로 합 j를 만들 수 있는가"를 저장합니다.
  • 각 원소에 대해 j를 sum/2부터 현재 원소의 값까지 역순으로 순회하며 갱신합니다. 역순 순회를 사용하면 같은 원소를 중복해서 사용하는 오류를 방지할 수 있습니다.
  • 모든 원소를 처리한 후 part[sum/2]의 값이 곧 최종 답이 됩니다.

이 방식은 2차원 테이블을 사용하는 일반적인 부분집합 합 DP를 1차원 배열로 공간 최적화한 형태로, 시간 복잡도는 O(n × sum/2)입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
bool findPartiion(int arr[], int n) {
    int sum = 0;
    int i, j;
    for (i = 0; i < n; i++)
        sum += arr[i];
    if (sum % 2 != 0)
        return false;
    bool part[sum / 2 + 1];
    for (i = 0; i <= sum / 2; i++) {
        part[i] = 0;
    }
    for (i = 0; i < n; i++) {
        for (j = sum / 2; j >= arr[i]; j--) {
            if (part[j - arr[i]] == 1 || j == arr[i])
                part[j] = 1;
        }
    }
    return part[sum / 2];
}
int main() {
    int arr[] = {
        6,
        4,
        8,
        12,
        15
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (findPartiion(arr, n) == true)
        cout << "Is possible to divide into two subsets of equal " "sum";
    else
        cout << "Is impossible to divide into two subsets" " of equal sum";
    return 0;
}

실행 결과

Is impossible to divide into two subsets of equal sum

마치며

이번 글에서는 파티션 문제를 재귀와 동적 계획법, 두 가지 방식으로 해결하는 방법과 C++ 코드를 살펴보았습니다. 동일한 로직은 Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 파티션 문제는 기본적인 코드이지만 부분집합 합, 배낭 문제 등 다양한 알고리즘 문제의 기반이 되므로, 원리를 확실히 익혀두면 여러 문제를 해결하는 데 큰 도움이 됩니다.