문제 소개
양의 정수만 포함된 비어 있지 않은 배열이 하나 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 이 배열을 두 개의 부분 집합으로 나누었을 때, 각 부분 집합에 속한 원소들의 합이 서로 같아질 수 있는지 판단하는 것입니다.
예를 들어 입력 배열이 [1, 5, 11, 5]라면 결과는 true(참)입니다. 이 배열은 [1, 5, 5]와 [11]이라는 두 부분 집합으로 나눌 수 있으며, 두 집합의 합이 모두 11로 동일하기 때문입니다.
접근 방법 및 알고리즘
이 문제는 본질적으로 '부분 집합 합(SubSet Sum)' 문제의 변형입니다. 두 부분 집합의 합이 같으려면 전체 합의 정확히 절반을 만들 수 있는 부분 집합이 존재해야 하므로, 동적 계획법(DP)을 활용해 해결할 수 있습니다. 다음 단계를 따릅니다.
- n := 배열의 크기
- sum := 0
- i를 0부터 n-1까지 반복하며 sum := sum + nums[i]
- sum이 홀수라면 false를 반환합니다. (두 부분 집합의 합이 같으려면 전체 합이 반드시 짝수여야 합니다.)
- sum := sum / 2
- 크기가 sum + 1인 dp 배열을 생성합니다.
- dp[0] := true
- i를 0부터 n-1까지 반복:
- x := nums[i]
- j를 sum부터 j - x까지 감소시키며 반복:
- dp[j] := dp[j] 또는 dp[j - x]
- 최종적으로 dp[sum]을 반환합니다.
여기서 중요한 포인트는 내부 반복문을 큰 인덱스에서 작은 인덱스 방향(역순)으로 진행한다는 것입니다. 역순으로 순회해야 각 원소가 한 번만 사용되도록 보장할 수 있으며, 이는 0/1 배낭(Knapsack) 문제와 동일한 원리입니다. 만약 정방향으로 순회하면 같은 원소를 여러 번 중복 사용하게 되어 잘못된 결과가 나올 수 있습니다.
이 알고리즘의 시간 복잡도는 O(n × sum), 공간 복잡도는 O(sum)입니다.
C++ 구현 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i =0;i<n;i++)sum+=nums[i];
if(sum&1)return false;
sum/=2;
vector <bool> dp(sum+1);
dp[0] = true;
for(int i =0;i<n;i++){
int x = nums[i];
for(int j =sum;j-x>=0;j--){
dp[j]=dp[j] || dp[j-x];
}
}
return dp[sum];
}
};
main(){
Solution ob;
vector<int> v = {1,5,11,5};
cout << ob.canPartition(v);
}
입력
[1,5,11,5]
출력
1
출력값 1은 해당 배열을 합이 같은 두 부분 집합으로 분할할 수 있음을 의미합니다.