<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/26957?tab=curriculum&amp;speed=2">파이썬 알고리즘 문제풀이</a>
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
<ul>
<li>문제</li>
</ul>
자연수 n, m이 주어지면 1부터 n까지의 숫자로 만들 수 있는 m개로 이루어진 순열의 목록과 총 수를 출력하는 프로그램을 작성하시오. 단, 중복을 허용하는 수열로 예를들면 [1, 1]과 같은 형태도 가능합니다.
<ul>
<li>입력예제</li>
</ul>
3, 2
<ul>
<li>출력예제</li>
</ul>
1 1 
1 2 
1 3 
2 1 
2 2 
2 3 
3 1 
3 2 
3 3 
9
<h2 id="내-풀이">내 풀이</h2>
<pre><code>func combination(_ n: Int, _ m: Int) {
 
 var res = [Int](repeating: 0, count: m)
 var cnt = 0
 
 func dfs(_ v:Int) {
 if v == m {
 for i in res {
 print(i, terminator: " ")
 }
 cnt+=1
 print()
 } else {
 for i in 1...n {
 res[v]=i
 dfs(v+1)
 }
 }
 }
 dfs(0)
 print(cnt)
}
combination(3, 2)</code></pre>
dfs와 재귀를 활용한 코드를 잘 이용하면 쉽게 구할 수 있는 문제이다. 모든 재귀함수에서 유의해야하듯 baseCase를 잘 설정해줘야하며 그 외에 유의할 사항은 없는 문제라고 볼 수 있다. res와 cnt값을 사용하기 위해 dfs를 nested function으로 구현했으며 별도로 전역변수로 사용 또는 inout을 활용하면 nested function으로 구현할 필요는 없다.
<h2 id="강의-풀이">강의 풀이</h2>
풀이로직에서 차이가 없기 때문에 파이썬코드만 살펴보겠다.
<h2 id="파이썬-코드">파이썬 코드</h2>
<pre><code>def DFS(L):
 global cnt
 if L==m:
 for j in range(m):
 print(res[j], end=' ')
 print()
 cnt+=1
 else:
 for i in range(1, n+1):
 res[L]=i
 DFS(L+1)

if __name__=="__main__":
 n, m = map(int, input().split())
 res=[0]*m
 cnt=0
 DFS(0)
 print(cnt)</code></pre></div></div>

PS & Algorithm

WooSeok Suh

중복순열 구하기
참고자료: 파이썬 알고리즘 문제풀이
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
문제
자연수 n, m이 주어지면 1부터 n까지의 숫자로 만들 수 있는 m개로 이루어진 순열의 목록과 총 수를 출력하는 프로그램을 작성하시오. 단, 중복을 허용하는 수열로 예를들면 [1, 1]과 같은 형태도 가능합니다.
입력예제
3, 2
출력예제
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
9
내 풀이
func combination(_ n: Int, _ m: Int) {
    var res = [Int](repeating: 0, count: m)
    var cnt = 0
    func dfs(_ v:Int) {
        if v == m {
            for i in res {
                print(i, terminator: " ")
            }
            cnt+=1
            print()
        } else {
            for i in 1...n {
                res[v]=i
                dfs(v+1)
            }
        }
    }
    dfs(0)
    print(cnt)
}
combination(3, 2)
dfs와 재귀를 활용한 코드를 잘 이용하면 쉽게 구할 수 있는 문제이다. 모든 재귀함수에서 유의해야하듯 baseCase를 잘 설정해줘야하며 그 외에 유의할 사항은 없는 문제라고 볼 수 있다. res와 cnt값을 사용하기 위해 dfs를 nested function으로 구현했으며 별도로 전역변수로 사용 또는 inout을 활용하면 nested function으로 구현할 필요는 없다.
강의 풀이
풀이로직에서 차이가 없기 때문에 파이썬코드만 살펴보겠다.
파이썬 코드
def DFS(L):
    global cnt
    if L==m:
        for j in range(m):
            print(res[j], end=' ')
        print()
        cnt+=1
    else:
        for i in range(1, n+1):
            res[L]=i
            DFS(L+1)
if __name__=="__main__":
    n, m = map(int, input().split())
    res=[0]*m
    cnt=0
    DFS(0)
    print(cnt)

완전탐색 - DFS(5)

댓글