조합의 수 계산
문제 : n개의 서로 다른 원소에서 m개를 선택하는 경우의 수
고등학교 수학시간에 배웠던 방법을 생각하면 다음과 같이 쉽게 풀어낼 수 있다.
from math import factorial as f
def combi(n,m):
return f(n)/(f(m)*f(n-m))
재귀적 방법으로 생각하려면 특정한 하나의 원소 입장에서 볼 때, 그 원소를 포함하는 경우와 그렇지 않은 경우를 따로 계산해서 더하면 된다.
def combi(n,m):
return combi(n-1,m) + combi(n-1,m-1)
이렇게 쓰면 될 것 같지만 trivial case가 빠져있다.
def combi(n,m):
if n == m:
return 1
elif m == 0:
return 1
else:
return combi(n-1,m) + combi(n-1, m-1)
다음과 같이 써야한다.
이번에는 효율성 측면에서 생각해보자. m과 n이 커지면 함수의 호출이 수 없이 이루어진다. 오히려 loop를 이용하는 것이 훨씬 효율적일 것이다.
예를 들어 Recursive Algorithm(1)에서 만들었던 Fibonacci 순열을 생각해보면
fibo(4)에 대한 해답을 구할 때
fibo(4) #1 = fibo(3) #2 + fibo(2) #3
= fibo(2) #4 + fibo(1) + fibo(1) + fibo(0)
= fibo(1) #5 + fibo(0) #6 + fibo(1) #7 + fibo(1) #8 + fibo(0) #9
도합 9번의 함수가 호출되는 것을 알 수 있다.
그렇다면 실행시간에는 어떻게 차이가 있는지 recursive version과 iterative version을 비교해보자.
import time
def rec(n):
if n <= 1:
return n
else:
return rec(n-1) + rec(n-2)
def iter(n):
if n <= 1:
return n
else:
i = 2
t0 = 0
t1 = 1
while i <= n:
t0, t1 = t1, t0 + t1
i += 1
return t1
while True:
nbr = int(input("Enter a number: "))
if nbr == -1:
break
m ,
ts = time.time()
fibo = iter(nbr)
ts = time.time() - ts
print("Iterative version: %d (%.3f)" % (fibo, ts))
ts = time.time()
fibo = rec(nbr)
ts = time.time() - ts
print("Recursive version %d (%.3f)" % (fibo, ts))
실행화면
Enter a number : 20
Iterative version : 6765 (0.000)
Recursive version : 6765 (0.003)
Enter a number : 30
Iterative version : 832040 (0.000)
Recursive version : 832040 (0.376)
Enter a number : 35
Iterative version : 9227465 (0.000)
Recursive version : 9227465 (4.166)
Comments