파티션 문제: 동적 계획법으로 합이 같은 두 부분집합으로 나눌 수 있는지 확인하기

이 문제에서는 주어진 집합을 각 부분집합의 합이 서로 같아지도록 두 개로 분할할 수 있는지 판별합니다.

가장 먼저 집합에 포함된 모든 원소의 합을 구해야 합니다. 합이 짝수라면 두 집합으로 나눌 가능성이 있지만, 홀수라면 절대로 균등하게 나눌 수 없습니다.

합이 짝수인 경우에는 partTable이라는 표를 만들어 다음 조건을 이용해 문제를 해결합니다.

partTable[i, j]는 배열의 array[0]부터 array[j-1]까지의 원소들만 사용해 합이 i인 부분집합을 만들 수 있으면 true, 그렇지 않으면 false입니다.

입력과 출력

입력:
정수 집합 {3, 1, 1, 2, 2, 1}

출력:
집합을 합이 같은 두 부분으로 나눌 수 있으면 True
여기서 답은 true이며, 한 가지 분할 예는 {3, 1, 1}, {2, 2, 1}입니다.

알고리즘

checkPartition(set, n)

입력 − 주어진 집합과 집합에 포함된 원소의 개수

출력 − 합이 같은 두 부분집합으로 분할이 가능하면 true, 불가능하면 false

Begin
   sum := 집합 내 모든 원소의 합
   if sum이 홀수이면
      return false

   (sum/2 + 1) × (n + 1) 크기의 partTable 생성
   0번째 행의 모든 값을 true로 설정
   0번째 열의 모든 값을 false로 설정

   for i := 1 to sum/2, do
      for j := 1 to n, do
         partTab[i, j] := partTab[i, j-1]
         if i >= set[j-1], then
            partTab[i, j] := partTab[i, j] OR partTab[i – set[j-1], j-1]
      done
   done

   return partTab[sum/2, n]
End

점화식 설명

표를 채우는 점화식은 다음과 같이 해석할 수 있습니다.

set[j-1]을 포함하지 않는 경우: partTab[i][j-1]의 값을 그대로 사용합니다.
set[j-1]을 포함하는 경우(i ≥ set[j-1]): 남은 합 i - set[j-1]을 이전 원소들로 만들 수 있는지 partTab[i - set[j-1]][j-1]을 확인합니다.

두 경우 중 하나라도 true이면 partTab[i][j]는 true가 됩니다. 최종적으로 partTab[sum/2][n]이 true라면, 전체 합의 절반에 해당하는 부분집합이 존재한다는 뜻이므로 나머지 원소들이 자동으로 또 다른 부분집합을 이루게 됩니다.

시간 및 공간 복잡도

시간 복잡도는 O(sum × n)이며, 공간 복잡도 역시 O(sum × n)입니다. 여기서 sum은 집합 원소들의 총합, n은 원소의 개수입니다.

C++ 구현 예제

#include <iostream>
using namespace std;

bool checkPartition(int set[], int n) {
   int sum = 0;

   for (int i = 0; i < n; i++)   // 집합의 모든 원소의 합을 구함
      sum += set[i];

   if (sum % 2 != 0)   // 합이 홀수이면 두 집합으로 나눌 수 없음
      return false;

   bool partTab[sum/2+1][n+1];   // 파티션 테이블 생성
   for (int i = 0; i <= n; i++)
      partTab[0][i] = true;   // 합이 0이면 빈 부분집합으로 항상 만들 수 있으므로 true

   for (int i = 1; i <= sum/2; i++)
      partTab[i][0] = false;   // 원소를 하나도 사용하지 않으면 양의 합을 만들 수 없으므로 false

   // 파티션 테이블을 바텀업(bottom-up) 방식으로 채움
   for (int i = 1; i <= sum/2; i++) {
      for (int j = 1; j <= n; j++) {
         partTab[i][j] = partTab[i][j-1];
         if (i >= set[j-1])
            partTab[i][j] = partTab[i][j] || partTab[i - set[j-1]][j-1];
      }
   }
   return partTab[sum/2][n];
}

int main() {
   int set[] = {3, 1, 1, 2, 2, 1};
   int n = 6;

   if (checkPartition(set, n))
      cout << "주어진 집합은 합이 같은 두 부분집합으로 나눌 수 있습니다.";
   else
      cout << "주어진 집합은 합이 같은 두 부분집합으로 나눌 수 없습니다.";
}

참고: 위 코드의 bool partTab[sum/2+1][n+1]처럼 실행 시점에 크기가 정해지는 배열(가변 길이 배열, VLA)은 GCC 등 일부 컴파일러에서만 지원되는 확장 기능입니다. 표준 C++에서는 std::vector<std::vector<bool>>를 사용하는 것이 안전합니다.

실행 결과

주어진 집합은 합이 같은 두 부분집합으로 나눌 수 있습니다.