문제 개요
숫자 리스트 nums가 주어졌을 때, 이 리스트를 두 그룹으로 나누어 각 그룹에 속한 원소들의 합이 서로 같아지도록 할 수 있는지 확인하는 프로그램을 만들어 보겠습니다.
예를 들어 입력이 nums = [2, 3, 6, 5]라면 출력은 True가 됩니다. [2, 6]과 [3, 5] 두 그룹으로 나누면 각각의 합이 8로 동일하기 때문입니다.
해결 접근 방법
이 문제는 전형적인 '동일한 부분 집합 분할(Partition Equal Subset Sum)' 문제로, 동적 계획법(DP)을 활용하면 효율적으로 해결할 수 있습니다. 해결 단계는 다음과 같습니다.
total := nums의 모든 원소의 합
total이 홀수라면 False 반환
half := total / 2의 정수 부분
dp := 크기가 half + 1인 리스트를 생성하고 모두 False로 초기화
dp[0] := True
nums의 각 num에 대해 다음을 반복
i를 half부터 0까지 1씩 감소시키며 반복
i >= num이라면 dp[i] := dp[i] OR dp[i - num]
dp[half] 반환
예제 코드
class Solution:
def solve(self, nums):
total = sum(nums)
if total & 1:
return False
half = total // 2
dp = [True] + [False] * half
for num in nums:
for i in range(half, 0, -1):
if i >= num:
dp[i] |= dp[i - num]
return dp[half]
ob = Solution()
nums = [2, 3, 6, 5]
print(ob.solve(nums))
입력
[2, 3, 6, 5]
출력
True
동작 원리 설명
전체 합이 홀수라면 두 그룹의 합을 같게 만드는 것 자체가 불가능하므로 즉시 False를 반환합니다. 전체 합이 짝수라면 문제는 '합이 total/2인 부분 집합을 찾을 수 있는가'와 동일해집니다.
여기서 dp 배열의 dp[i]는 "주어진 숫자들 중 일부를 선택하여 합 i를 만들 수 있는가"를 의미합니다. 각 숫자를 순회하면서 인덱스를 뒤에서부터 앞으로 갱신하는데, 이는 하나의 숫자가 한 그룹에서 중복해서 사용되는 것을 방지하기 위함입니다. 최종적으로 dp[half]가 True라면 합이 같은 두 그룹으로 분할이 가능하다는 뜻입니다.
이 알고리즘의 시간 복잡도는 O(n × half), 공간 복잡도는 O(half)입니다. 여기서 n은 리스트의 원소 개수, half는 전체 합의 절반입니다.