이번에 알아볼 알고리즘은 우리가 중고등학교 때에 엄청나게 머리를 아프게 했던 확률에서 매우 중요하게 사용되는 조합(Combinations)의 수를 구하는 방법입니다. 흔히 수식으로 알려져 있는 이것은 \[{n\choose k} = \frac{n!}{(n-k)!k!}\] 라고 쓸 수 있는데요, 이것을 어떻게 하면 효율적으로 구할 수 있는지 알아보겠습니다.
먼저 가장 간단하게 생각할 수 있는 것은 factorial함수를 구현한 다음에 수식 그대로 값을 계산하는 것입니다.
#팩토리얼 값을 구하는 함수
def factorial(n):
if n <= 1:
return 1
else:
result = 1
for i in range(2, n+1):
result *= i
return result
#각각의 팩토리얼을 구해서 계산한 값을 리턴합니다.
def NChooseK_slow(n, k):
return factorial(n)/(factorial(k)*factorial(n-k))이제 결과 값이 맞는지 확인해 보면,
>>> print NChooseK_slow(6,3)
20잘 나온다는 것을 확인하실 수 있습니다 ^^
하지만 조금만 더 생각해 보면 이 방법은 굉장히 비효율적일 수 있다는 생각이 드실 겁니다. 왜냐하면 factorial 값을 구하는 것도 꽤나 비용이 크고, 분명히 중복되는 연산도 있을테구요. 결론적으로 우리가 중학교 때에 사용했던 쉬운 계산법($n$부터 $k$개를 곱한 것을 $k!$로 나눠줘라.)을 이용하여 계산한다면 훨씬 더 간단할 것 같죠?
먼저, Slow 방법으로 구하게 되면, 분자에 $n!$에 의해 $n$번, 분모에 $n-k$번과 $k$번을 합쳐서 총 $2n$번의 연산을 하게 되지만, Fast 방법에서는 분모 분자에 각각 $k$번씩 연산하므로 $2k$번의 연산을 하게 됩니다. 여기서 중요한 또 하나의 포인트는 ${n \choose k}={n \choose n-k}$이므로 $k$와 $n-k$중 더 작은 값을 선택하는 것입니다. 그럼 이 방법으로 구현해 보고 얼마나 효율성에 차이가 나는지 확인해 보겠습니다.
def NChooseK_fast(n, k):
numerator = 1
denominator = 1
k = min(n-k, k) #조합의 대칭성을 이용하여 더 적은 수의 연산을 하기 위해서입니다.
for i in range(1, k+1):
denominator *= i
numerator *= n+1-i
return numerator/denominator
>>> print NChooseK_fast(6,3)
20마찬가지로 결과는 잘 뽑아내는것 같네요^^ 그럼 이제 효율성을 비교해 보겠습니다.
>>> from time import time
>>> t0 = time()
>>> NChooseK_slow(10000, 1000)
>>> print "걸린시간 : %.4f" % (time()-t0)
걸린시간 : 0.0543
>>> t0 = time()
>>> NChooseK_fast(10000, 1000)
>>> print "걸린시간 : %.4f" % (time()-t0)
걸린시간 : 0.0012와우.. 고작 10000정도를 입력했는데 시간 차이가 무려 50배 가까이 나네요.. 수가 커질수록 그 차이는 더 심해지겠죠? ^^ 작은 차이가 엄청난 속도 차이로 벌어질 수 있다는 점 명심하세요~