<div id="readability-page-1" class="page"><div><h2 id="합이-같은-부분-집합">합이 같은 부분 집합</h2>
참고자료: <a href="https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8/lecture/26955?tab=curriculum&amp;speed=2">파이썬 알고리즘 문제풀이</a>
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
<ul>
<li>문제</li>
</ul>
n개의 숫자로 구성된 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 같은 경우가 있다면 "YES"아니면 "NO"를 출력하는 프로그램을 작성하시오.
<ul>
<li>입력예제</li>
</ul>
6 
1 3 5 6 7 10
<ul>
<li>출력예제</li>
</ul>
"YES"
<h2 id="내-풀이">내 풀이</h2>
<pre><code>import Foundation

func dfs(_ idx: Int, _ sum: Int) {
 if sum&gt;total/2 { return }
 if idx == n {
 if sum==(total-sum) {
 print("YES")
 exit(0)
 }
 } else {
 dfs(idx+1, sum+a[idx])
 dfs(idx+1, sum)
 }
}

let n = Int(readLine()!)!
let a = readLine()!.split{$0==" "}.map{Int(String($0))!}
var total = a.reduce(0, +)
dfs(0, 0)
print("NO")</code></pre>
<ul>
<li>시간복잡도 측면에서 유리한 점을 가져가기 위해, 일단 sum이 total/2보다 커지는 경우는 바로 함수를 종료시켰다. 현재까지 탐색한 부분집합의 합(sum)이 total/2보다 크다면 더이상 볼 필요도 없이 두 부분집합의 합이 같을 수가 없기 때문이다.</li>
</ul>
dfs로 넘기는 (0, 0)은 각 index와 부분집합의 합 sum이다. idx가 n과 같은 경우에는 함수를 종료해야하는 BaseCase가 되고 이때 total-sum과 sum이 같다면 A라는 집합을 두 개의 부분집합으로 나누었을 때, 두 부분집합의 합이 같다는 의미가 되고 "YES"를 출력하고 프로그램을 종료한다.
idx가 n에 도달하기 전까지는 숫자를 idx를 1씩 증가시키면서 부분집합의 합(sum)에 a[idx]를 더하는 경우와 더하지 않는 경우를 나눠서 dfs를 호출한다.
<h2 id="강의-풀이">강의 풀이</h2>
풀이로직에서 차이가 없기 때문에 파이썬코드만 살펴보겠다.
<h2 id="파이썬-코드">파이썬 코드</h2>
<pre><code>import sys

def DFS(L, sum):
 if sum &gt; (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)
 
n=int(input())
a=list(map(int, input().split()))
total=sum(a)
DFS(0, 0)
print("NO")</code></pre></div></div>

PS & Algorithm

WooSeok Suh

합이 같은 부분 집합
참고자료: 파이썬 알고리즘 문제풀이
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
문제
n개의 숫자로 구성된 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 같은 경우가 있다면 "YES"아니면 "NO"를 출력하는 프로그램을 작성하시오.
입력예제
6
1 3 5 6 7 10
출력예제
"YES"
내 풀이
import Foundation
func dfs(_ idx: Int, _ sum: Int) {
    if sum>total/2 { return }
    if idx == n {
        if sum==(total-sum) {
            print("YES")
            exit(0)
        }
    } else {
        dfs(idx+1, sum+a[idx])
        dfs(idx+1, sum)
    }
}
let n = Int(readLine()!)!
let a = readLine()!.split{$0==" "}.map{Int(String($0))!}
var total = a.reduce(0, +)
dfs(0, 0)
print("NO")
시간복잡도 측면에서 유리한 점을 가져가기 위해, 일단 sum이 total/2보다 커지는 경우는 바로 함수를 종료시켰다. 현재까지 탐색한 부분집합의 합(sum)이 total/2보다 크다면 더이상 볼 필요도 없이 두 부분집합의 합이 같을 수가 없기 때문이다.
dfs로 넘기는 (0, 0)은 각 index와 부분집합의 합 sum이다. idx가 n과 같은 경우에는 함수를 종료해야하는 BaseCase가 되고 이때 total-sum과 sum이 같다면 A라는 집합을 두 개의 부분집합으로 나누었을 때, 두 부분집합의 합이 같다는 의미가 되고 "YES"를 출력하고 프로그램을 종료한다.
idx가 n에 도달하기 전까지는 숫자를 idx를 1씩 증가시키면서 부분집합의 합(sum)에 a[idx]를 더하는 경우와 더하지 않는 경우를 나눠서 dfs를 호출한다.
강의 풀이
풀이로직에서 차이가 없기 때문에 파이썬코드만 살펴보겠다.
파이썬 코드
import sys
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)
n=int(input())
a=list(map(int, input().split()))
total=sum(a)
DFS(0, 0)
print("NO")

완전탐색 - DFS(3)

댓글