백트래킹 알고리즘: Subset Sum 문제 (Backtracking algorithm)

Backtracking algorithm

학습 : Chan-Su Shin (신찬수): 알고리즘 - Backtracking - Subset Sum

https://www.youtube.com/watch?v=SSSTVXj_JNk&list=PLsMufJgu5932XYejsOwcUDJ2F75f56nrl&index=39

 

 

 

Subset Sum 문제

• A의 집합이 주어지면 원소들의 합으로 S가 되는 부분집합을 찾는문제

첫 번째 방법: pseudo code

SubsetSum1(A, S):

    if S == 0: return True
    elif S < 0: return False
    else:  # 0 < S
        pick z from A  ※ A[i]
        with = SubsetSum1(A - {z}, S - z)  # z를 뽑은 경우
        wout = SubsetSum1(A - {z}, S)      # z를 안뽑은 경우
        return with or wout

두번째 방법: pseudo code

SubsetSum2(A, i, S):   # {A[0], … A[i]} → S가 되는 Subset

    if S == 0: return True
    elif S < 0 or i == -1: return False   # A가 공집합이거나 S가 만족하지 않을 때
    else:
        with = SubsetSum2(A, i-1, S - A[i])   
        wout = SubsetSum2(A, i-1, S)          
        return with or wout

 

• A 집합을 리스트로 변경
• 초기 함수를 부를 땐 SubsetSum2(A, |A| - 1, S)
• 위 함수를 아래와같이 나타내면 전형적인 DP 점화식이 된다.

• DP로 보고 DP 테이블을 살펴보자 

• 수행시간이 O(nS)가 되고 n에 관한 다항식이 아닌 입력 값이 수행시간에 등장한다.
• S의 값이 10억처럼 큰 수가오면 바람직하지 않게된다. → Pseudo Polynomial

세번째 방법: pseudo code (Backtracking 활용)

SubsetSum(k):   # x[k]

current_sum = 현재까지 선택된 A의 값의 합

if k ≥ len(A):   # x[0] ... x[n-1] 까지 결정
  └ if current_sum == S : print(x)   ※ 해 출력
else:   # x[k] 결정
  x[k] = 1
  SubsetSum(k + 1)

  x[k] = 0
  SubsetSum(k + 1)

• 위와 같이 백트래킹 알고리즘으로 해결할 수 있지만 몇가지 수정하면 시간을 절약할 수 있다.

백트래킹 시간절약 버전 

• 위와 같이 A를 먼저 정렬한 후 부분합을 계산하면 S가 넘을 경우 다음 원소들에 대해선 함수를 호출할 필요가 없어진다. 

SubsetSum(k):   # x[k]

current_sum = 현재까지 선택된 A의 값의 합

if k ≥ len(A):   # x[0] ... x[n-1] 까지 결정
  └ if current_sum == S : print(x)   ※ 해 출력
else:   # x[k] 결정
  if current_sum + A[k] <= S:
    x[k] = 1
    SubsetSum(k+1)

  x[k] = 0
  SubsetSum(k+1)