Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 해결하는 부분집합 합(SubSet Sum) 문제

이 글에서는 아래의 문제에 대한 해결 방법을 단계별로 알아보겠습니다.

문제 정의

문제 — 음수가 아닌 정수로 구성된 배열과 목표 합(sum)이 주어졌을 때, 배열의 부분집합 중에서 원소들의 합이 목표 값과 정확히 일치하는 부분집합이 존재하는지 판별하는 것이 목표입니다.

예를 들어 집합이 [2, 14, 6, 22, 4, 8]이고 목표 합이 10이라면, {2, 8} 또는 {6, 4}의 합이 10이므로 답은 '존재한다'가 됩니다.

방법 1: 재귀를 이용한 완전 탐색 (Naive Approach)

가장 직관적인 방법은 각 원소마다 두 가지 경우를 모두 재귀적으로 탐색하는 것입니다.

  • 마지막 원소를 부분집합에 포함하는 경우
  • 마지막 원소를 부분집합에서 제외하는 경우

모든 조합을 검사하므로 시간 복잡도는 O(2n)입니다.

예제 코드

def subset_sum(num_set, n, target):
    # 기저 사례: 목표 합이 0이면 빈 부분집합으로 성립
    if target == 0:
        return True
    # 원소를 모두 사용했는데도 합이 남아 있으면 실패
    if n == 0 and target != 0:
        return False
    # 마지막 원소가 목표 합보다 크면 제외하고 진행
    if num_set[n - 1] > target:
        return subset_sum(num_set, n - 1, target)
    # (1) 마지막 원소를 포함하는 경우
    # (2) 마지막 원소를 제외하는 경우
    return subset_sum(num_set, n - 1, target) or \
           subset_sum(num_set, n - 1, target - num_set[n - 1])

# 메인 실행부
num_set = [2, 14, 6, 22, 4, 8]
target = 10
n = len(num_set)

if subset_sum(num_set, n, target):
    print("주어진 합을 만족하는 부분집합이 존재합니다")
else:
    print("주어진 합을 만족하는 부분집합이 없습니다")

출력 결과

주어진 합을 만족하는 부분집합이 존재합니다

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

재귀 방식은 같은 하위 문제를 여러 번 반복 계산하기 때문에 입력이 커지면 매우 비효율적입니다. 동적 계획법에서는 2차원 테이블(dp)에 중간 결과를 저장해 중복 계산을 제거합니다.

dp[i][j]는 '처음 i개의 원소만 사용했을 때 합 j를 만들 수 있는가?'를 의미하며, 점화식은 다음과 같습니다.

  • 목표 합 j가 0이면 → 항상 True (아무것도 선택하지 않으면 됨)
  • i번째 원소가 j보다 크면 → dp[i][j] = dp[i-1][j]
  • 그 외의 경우 → dp[i][j] = dp[i-1][j] 또는 dp[i-1][j - arr[i-1]]

시간 복잡도와 공간 복잡도 모두 O(n × sum)으로, 완전 탐색보다 훨씬 효율적입니다.

예제 코드

def is_subset_sum(arr, n, target):
    # dp[i][j]: 처음 i개의 원소로 합 j를 만들 수 있는지 여부
    dp = [[False] * (target + 1) for _ in range(n + 1)]

    # 합이 0인 경우: 빈 부분집합으로 항상 만들 수 있음
    for i in range(n + 1):
        dp[i][0] = True

    # 테이블을 아래에서 위로 채워 나감
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if arr[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]

    return dp[n][target]

# 메인 실행부
arr = [2, 14, 6, 22, 4, 8]
target = 10
n = len(arr)

if is_subset_sum(arr, n, target):
    print("주어진 합을 만족하는 부분집합이 존재합니다")
else:
    print("주어진 합을 만족하는 부분집합이 없습니다")

출력 결과

주어진 합을 만족하는 부분집합이 존재합니다

결론

이 글에서는 파이썬으로 부분집합 합(SubSet Sum) 문제를 해결하는 두 가지 방법을 살펴보았습니다. 재귀를 이용한 완전 탐색은 구현이 간단하지만 O(2n)의 시간이 걸리는 반면, 동적 계획법은 O(n × sum)으로 최적화할 수 있습니다. 따라서 입력 크기가 커질 가능성이 있다면 동적 계획법을 사용하는 것이 바람직합니다.