Algorithm - 합이 같은 부분집합(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[합이 같은 부분집합(DFS)]

 

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나눈다. 이 때, 두 부분집합의 원소를 모두 더한 값이 서로 같으면 "YES"를 출력하고 그렇지 않으면 "NO"를 출력하는 프로그램을 작성하시오.

 

참고로, 둘로 나뉘는 두 부분집합은 서로소 집합이며 두 부분집합을 합하면 입력으로 주어지는 원래의 집합이 되어야 한다. 예를 들면, {1, 3, 5, 6, 7, 10}의 집합이 입력되면 {1, 3, 5, 7} = {6, 10}으로 두 부분집합의 합이 모두 16인 경우가 존재한다.

 

 

*입력 설명

첫 번째 줄에 자연수 N(1 ≤ N ≤ 10)이 주어진다.

두 번째 줄에 집합의 원소가 N개 주어진다. (단, 각 원소는 중복되지 않음)

 

*출력 설명

첫 번째 줄에 "YES" 또는 "NO"를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_46.txt', 'rt')

def DFS(L, sum):
    if sum > total//2:
        return
    if L == n:
        if sum == (total - sum):
            print("YES")
            sys.exit(0)
    else:
        DFS(L+1, sum+a[L])
        DFS(L+1, sum)

if __name__=="__main__":
    n = int(input())
    a = list(map(int, input().split()))
    total = sum(a)
    DFS(0, 0)
    print("NO")
    
# 출력 : YES

 

input_46.txt(입력)

6
1 3 5 6 7 10

 

 

중요내용

1. DFS() 함수의 인자 L은 리스트 a의 인덱스 번호를 의미한다.
2. DFS() 함수의 인자 sum은 자신이 만든 부분집합 원소의 총합을 의미한다.
3. DFS(L+1, sum+a[L]) 코드는 리스트 a의 인덱스 번호가 L인 벨류 값을 부분집합의 원소로 사용하겠다는 의미이다.
4. DFS(L+1, sum) 코드는 리스트 a의 인덱스 번호가 L인 벨류 값을 부분집합의 원소로 사용하지 않겠다는 의미이다.
5. sys.exit(0)는 해당 코드가 돌아가는 프로그램을 종료시키는 코드이다.
6. if sum > total // 2 는 해당 프로그램의 시간 복잡도를 개선하기 위한 코드이다.
7. 즉, total을 2로 나눈 몫보다 sum의 값이 커지면 결국 문제에서 원하는 결과(YES)를 얻지 못하기 때문에 나머지 탐색을 할 필요가 없다.
8. 따라서 if절의 조건이 sum > total // 2인 경우에는 return을 사용하여 재귀함수(DFS() 함수)를 종료시키고, 불필요한 탐색을 방지하여 시간 복잡도를 개선하는 것이다.