0Pricing
DSA Interview Prep · 강의

동일한 부분집합 합으로 분할

분할 문제를 전체 합의 절반을 목표로 하는 0/1 배낭 문제로 바꾸고, 불리언 DP 배열로 가능 여부를 판별합니다.

동일한 부분집합 합으로 분할은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

문제 설명

양의 정수로 이루어진 비어 있지 않은 배열 nums가 주어졌을 때, 이를 합이 같은 두 부분 집합으로 나눌 수 있는지 판별합니다. 예를 들어 [1, 5, 11, 5]는 [1, 5, 5]와 [11]로 나눌 수 있으며 두 부분 집합의 합은 모두 11입니다. 전체 합이 홀수이면 답은 즉시 False가 됩니다. 그렇지 않으면 total_sum // 2의 합을 갖는 부분 집합을 찾아야 합니다. 이는 고전적인 부분 집합 합 문제입니다.

부분집합 합으로의 환원

핵심 환원은 다음과 같습니다. 전체 합 S가 짝수이고 어떤 부분집합의 합이 S//2라면, 나머지 원소들의 합도 자동으로 S//2가 됩니다. 따라서 부분집합 합 균등 분할은 어떤 부분집합의 합이 S//2인지 확인하는 문제로 환원됩니다. 이는 고전적인 NP-완전 부분집합 합 문제이며, 0/1 배낭 DP를 사용해 O(n × S) 시간에 해결합니다.

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False  # odd sum: impossible
    target = total // 2
    # Now: does any subset of nums sum to target?

불리언 DP 배열

부분집합의 합이 정확히 c가 되는 경우가 존재한다는 뜻으로 dp[c]라는 불리언 배열을 정의합니다. dp[0] = True로 초기화하고(빈 부분집합의 합은 0입니다), 나머지는 모두 False로 설정합니다. 각 숫자 num에 대해 용량을 target에서 num까지 역방향으로 순회한 뒤(0/1 배낭의 역방향 순회), dp[c] = dp[c] or dp[c - num]으로 설정합니다.

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for c in range(target, num - 1, -1):  # backward: 0/1 knapsack
            dp[c] = dp[c] or dp[c - num]
    
    return dp[target]

print(canPartition([1, 5, 11, 5]))  # True
print(canPartition([1, 2, 3, 5]))   # False

예제를 따라가며 확인하기

[1, 5, 11, 5]의 경우 총합은 22이고 목표값은 11입니다. 처음에는 dp[0]=True입니다. 1을 처리한 후에는 dp[1]=True가 됩니다. 5를 처리한 후에는 dp[5]=True, dp[6]=True가 됩니다. 11을 처리한 후에는 dp[11]=True가 됩니다(11만 사용한 결과입니다). 이미 합 11이 가능하다는 사실을 확인했지만, 모든 숫자를 계속 처리합니다. 최종 답은 dp[11]=True이므로 분할이 가능합니다.

조기 종료 최적화

dp[target]이 어느 시점에서든 True가 되면 즉시 True를 반환하도록 조기 종료를 추가할 수 있습니다. 이렇게 하면 최선의 경우 실행 속도를 크게 높일 수 있습니다. 또한 단일 원소가 target과 같다면 즉시 True를 반환할 수 있습니다. 단일 원소가 target보다 크다면 목표값을 만드는 어떤 부분집합에도 포함될 수 없지만, 나머지 원소는 계속 확인해야 합니다.

def canPartition_fast(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    if max(nums) > target:  # any element > target makes it impossible
        return False
    
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for c in range(target, num - 1, -1):
            dp[c] = dp[c] or dp[c - num]
            if dp[target]:
                return True  # early exit
    
    return dp[target]

print(canPartition_fast([1, 5, 11, 5]))  # True

DP 배열 대신 파이썬 집합 사용하기

또 다른 방법은 도달 가능한 합의 집합을 유지하는 것입니다. {0}에서 시작합니다. 각 숫자를 현재 집합의 모든 합에 더합니다: reachable = reachable | {s + num for s in reachable}. 목표값을 넘지 않는 합만 남기도록 필터링합니다. 마지막에는 집합에 target이 포함되어 있는지 확인합니다. 이 방법은 직관적이지만 더 많은 메모리를 사용할 수 있고 실제 실행에서는 느릴 수 있습니다.

def canPartition_set(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    
    reachable = {0}
    for num in nums:
        reachable = {s + num for s in reachable if s + num <= target} | reachable
    
    return target in reachable

print(canPartition_set([1, 5, 11, 5]))  # True

복잡도 분석

DP 방식은 S = sum(nums)일 때 O(n × S) 시간이 걸리며, 불리언 배열에 O(S) 공간을 사용합니다. LeetCode의 제약 조건(n ≤ 200, 합 ≤ 20,000)에서는 최대 4,000,000번의 연산이므로 매우 빠릅니다. 집합 방식도 점근적 복잡도는 같지만, 집합을 생성하는 데 따른 오버헤드 때문에 실제로는 더 느릴 수 있습니다.

합이 목표값인 부분집합 개수 세기

관련 문제로, 합이 목표값이 되는 부분집합의 개수를 세는 문제가 있습니다. DP를 불리언 값에서 정수로 변경합니다: dp[c] = number of ways to reach sum c. OR 대신 덧셈을 사용합니다: dp[c] += dp[c - num]. dp[0] = 1로 초기화하고, 동일하게 역방향으로 순회합니다. 이 일반화는 부분집합에 관한 여러 질문에 맞춰 배낭 문제의 틀을 어떻게 조정할 수 있는지 보여 줍니다.

def count_subsets(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    for num in nums:
        for c in range(target, num - 1, -1):
            dp[c] += dp[c - num]
    return dp[target]

print(count_subsets([1, 1, 1, 1, 1], 3))  # 10 (C(5,3))

면접에서 자주 나오는 추가 질문

다음과 같은 추가 질문을 예상해야 합니다. (1) 실제 분할 결과를 반환해야 한다면 어떻게 하나요? — 결과를 복원하려면 2차원 DP가 필요합니다. (2) 원소가 음수일 수 있다면 어떻게 하나요? — 목표값을 이동하거나 배열 대신 사전을 사용합니다. (3) 시간 복잡도는 어떻게 되나요? — O(n × 합)입니다. (4) 같은 숫자가 많다면 개선할 수 있나요? — 가능합니다. 빈도 계산을 사용해 바깥쪽 반복 횟수를 줄일 수 있습니다. 이러한 장단점은 항상 먼저 언급하는 것이 좋습니다.

0/1 배낭 문제와 연결하기

부분집합 합 균등 분할은 0/1 배낭 문제를 직접 적용한 것입니다. 물건은 숫자이고, 가중치는 값과 같으며, 배낭의 용량은 목표값과 같습니다. 최대 값이 얼마인지가 아니라 최대 값이 목표값과 같은지(가능 여부)를 확인합니다. 역방향 순회는 동일하고, 연산만 max에서 불리언 or로 바뀝니다. 면접에서 이러한 연결을 알아보면 강한 패턴 인식 능력을 보여 줄 수 있습니다.

경계 사례

다음과 같은 경계 사례를 처리해야 합니다. (1) 길이가 1인 배열 — 단일 원소는 나눌 수 없으므로 항상 False입니다. (2) 모든 원소가 같고 개수가 짝수인 경우 — 각 원소의 값에 따라 가능할 수도, 불가능할 수도 있습니다. (3) 합이 매우 큰 경우 — DP 배열을 할당하기 전에 제약 조건을 확인해야 합니다. (4) 목표값보다 큰 원소 — 목표값을 만드는 부분집합에 절대 포함될 수 없으므로 건너뛸 수 있습니다. 최댓값을 확인해 조기 종료하면 (4)를 효율적으로 처리할 수 있습니다.

빠른 확인

이번 레슨에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보세요.

학습 내용 정리

이번 레슨에서는 다음을 배웠습니다. 부분집합 합 균등 분할은 목표값을 총합//2로 하는 부분집합 합 문제로 환원됩니다. 불리언 1차원 DP dp[c]는 0/1 배낭과 동일한 역방향 순회를 사용합니다. 또한 불리언 OR을 정수 덧셈으로 바꾸면 부분집합 개수 세기로 일반화할 수 있습니다. 다음에는 부호 할당을 부분집합 합 차이에 대한 배낭 문제로 변환하는 목표 합 문제를 다룹니다.

자주 묻는 질문

“동일한 부분집합 합으로 분할” 강의는 무료인가요?

네 — “동일한 부분집합 합으로 분할” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“동일한 부분집합 합으로 분할”에서 뭘 배우나요?

분할 문제를 전체 합의 절반을 목표로 하는 0/1 배낭 문제로 바꾸고, 불리언 DP 배열로 가능 여부를 판별합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

“동일한 부분집합 합으로 분할” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. 0/1 배낭과 공간 최적화
  2. 무한 배낭과 동전 교환 II
  3. 동일한 부분집합 합으로 분할
  4. 양수와 음수 부호를 사용한 목표 합
← DSA Interview Prep(으)로 돌아가기