<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/26954?tab=curriculum&amp;speed=2">파이썬 알고리즘 문제풀이</a>
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
<ul>
<li>문제</li>
</ul>
자연수 n이 주어지면 1부터 해당 수까지의 부분집합을 모두 출력하는 프로그램을 작성하시오. 단, 공집합은 출력하지 않는다.
<ul>
<li>입력예제</li>
</ul>
3
<ul>
<li>출력예제</li>
</ul>
1 2 3 
1 2 
1 3 
1 
2 3 
2 
3
<h2 id="내-풀이">내 풀이</h2>
<pre><code>func subSet(_ v: Int) {
 if v &gt; n {
 for i in 1...n {
 if ch[i]==true{
 print(i, terminator:" ")
 }
 }
 print()
 } else {
 ch[v]=true
 subSet(v+1)
 ch[v]=false
 subSet(v+1)
 }
}

let n = Int(readLine()!)!
var ch = [Bool](repeating: false, count: n+1)
if n &lt;= 0 { print(-1) }
else { subSet(1) }</code></pre>
<ul>
<li>true / false == 포함하는경우 / 포함하지 않는 경우</li>
</ul>
이번에도 재귀함수를 활용한 깊이 우선 탐색 방법이다. checkList(ch)를 만들어서 해당 수(v)를 포함하는 경우와 그렇지 않은 경우를 구분해서 출력한다.
예를들어, 3까지의 부분집합을 구하기 위해서는 1에 대한 true / false, 2에 대한 true / false, 3에 대한 true / false를 모두 구해야한다. 그렇기 때문에 총 2x2x2 = 8가지의 부분집합이 출력되야 한다(공집합을 제외할 경우는 -1).
<h2 id="강의-풀이">강의 풀이</h2>
풀이로직에서 차이가 없기 때문에 파이썬코드만 살펴보겠다.
<h2 id="파이썬-코드">파이썬 코드</h2>
<pre><code>def DFS(v):
 if v==n+1:
 for i in range(1, n+1):
 if ch[i]==1:
 print(i, end=' ')
 print()
 else:
 ch[v]=1
 DFS(v+1)
 ch[v]=0
 DFS(v+1)

n=int(input())
ch=[0]*(n+1)
DFS(1)</code></pre></div></div>

PS & Algorithm

WooSeok Suh

부분집합 구하기
참고자료: 파이썬 알고리즘 문제풀이
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
문제
자연수 n이 주어지면 1부터 해당 수까지의 부분집합을 모두 출력하는 프로그램을 작성하시오. 단, 공집합은 출력하지 않는다.
입력예제
3
출력예제
1 2 3 
1 2 
1 3 
1 
2 3 
2 
3 
내 풀이
func subSet(_ v: Int) {
 if v > n {
 for i in 1...n {
 if ch[i]==true{
 print(i, terminator:" ")
 }
 }
 print()
 } else {
 ch[v]=true
 subSet(v+1)
 ch[v]=false
 subSet(v+1)
 }
}
let n = Int(readLine()!)!
var ch = [Bool](repeating: false, count: n+1)
if n <= 0 { print(-1) }
else { subSet(1) }
true / false == 포함하는경우 / 포함하지 않는 경우
이번에도 재귀함수를 활용한 깊이 우선 탐색 방법이다. checkList(ch)를 만들어서 해당 수(v)를 포함하는 경우와 그렇지 않은 경우를 구분해서 출력한다. 
예를들어, 3까지의 부분집합을 구하기 위해서는 1에 대한 true / false, 2에 대한 true / false, 3에 대한 true / false를 모두 구해야한다. 그렇기 때문에 총 2x2x2 = 8가지의 부분집합이 출력되야 한다(공집합을 제외할 경우는 -1).
강의 풀이
풀이로직에서 차이가 없기 때문에 파이썬코드만 살펴보겠다.
파이썬 코드
def DFS(v):
 if v==n+1:
 for i in range(1, n+1):
 if ch[i]==1:
 print(i, end=' ')
 print()
 else:
 ch[v]=1
 DFS(v+1)
 ch[v]=0
 DFS(v+1)
n=int(input())
ch=[0]*(n+1)
DFS(1)

완전탐색 - DFS(2)

댓글