파이썬 재귀호출 알고리즘 팩토리얼 구하기 #5

파이썬 재귀호출 알고리즘 팩토리얼 구하기 #5

 

안녕하세요.

오늘은 파이썬으로 공부하는 알고리즘 5번째 시간 팩토리얼 구하기입니다.

많은 분들이 개발언어를 다루면서 꼭 한 번은 접하는 것이고요. 정보처리기사에서도 꼭 출제되는 문제이기도 합니다.

하지만, 초보자들도 계시므로, 팩토리얼의 개념에 대해서 먼저 알아보겠습니다.

1! = 1
3! = 1 * 2 * 3 = 6
5! = 1 * 2 * 3 * 4 * 5 = 120
n! = 1 * 2 * 3 * 4 * 5 .... * (n-1) * n

이런 것이 팩토리얼입니다.

단, 0! = 1이라고 약속합니다.

팩토리얼 구하는 알고리즘은 우리가 첫 시간에 다루었던 1 ~ n까지의 합을 구하는 알고리즘을 조금 수정하면 쉽게 구하실 수 있습니다.

합을 구하는 알고리즘에서 덧셈을 곱셈으로 바꿔주기만 하면 쉽게 구할 수 있겠죠?

# n까지의 합을 구하는 알고리즘 보러 가기

2020/01/29 - [DB엔지니어가 공부하는 python] - [파이썬_알고리즘] 1 부터 n까지의 합 구하기 #2

[파이썬_알고리즘] 1 부터 n까지의 합 구하기 #2

그럼 파이썬 소스 한번 확인해보겠습니다.

간단하게..

def fact(n):
    f = 1                      # 곱을 계산할 변수, 초깃값은 1
    for i in range(1, n + 1):  # 1부터 n까지 반복(n+1은 제외)
        f = f * i              # 곱셈 연산으로 수정
    return f

print(fact(1))   # 1! = 1
print(fact(5))   # 5! = 120
print(fact(10))  # 10! = 3628800

 

 

이렇게 간단하게 파이썬 알고리즘을 구현할 수 있습니다.

자, 그럼 다른 방법이 있는지도 한번 확인해 보겠습니다.

팩토리얼 구하는 알고리즘은 <재귀 호출> 방식으로도 구현할 수 있습니다.

<재귀 호출> 이란, 어떤 함수 안에서 자기 자신을 다시 호출하는 것을 말합니다.

이걸 어떻게 팩토리얼 알고리즘에 구현하느냐 하면, 그 알고리즘은 아래와 같습니다.

1! = 1
2! = 2 * 1 = 2 * 1!
4! = 4 * (3 * 2 * 1) = 4 * 3!
...
n! = n * (n-1)!  <---- 팩토리얼 값을 구하기 위해 팩토리얼을 다시 호출함

위와 같은 알고리즘에 따라 파이썬 소스를 작성해볼까요?

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

print(fact(1))   # 1! = 1
print(fact(5))   # 5! = 120
print(fact(10))  # 10! = 3628800

위와 같은 소스가 완성되었습니다.

알고리즘을 분석해보겠습니다.

팩토리얼이란, 연속한 수의 곱셈으로 알고리즘이 이루어지는데요,

첫 번째 팩토리얼 알고리즘의 경우 n! 의 값을 구하기 위해서는 곱셈이 n번 필요합니다.

그렇다면, 두 번째 팩토리얼 알고리즘은 어떨까요? 계산과정을 노트에 써보시면 아시겠지만 n! 의 값을 구하기 위해서 두 번째 알고리즘은 n-1번의 곱셈이 필요합니다.

즉, 두 가지 방법 모두 O(n)의 계산 복잡도를 가지고 있습니다.

따라서, 별 차이 없어 보이긴 합니다.

하지만, 하나의 문제 해결을 위해서 두 가지 방법을 알고 있다는 건 분명 좋은 일입니다.

오늘 우리는 팩토리얼 구하기를 공부해 봤습니다.

다음 이 시간에 다시 돌아오겠습니다.

항상, 읽어주셔서 감사드립니다.

팩토리얼

 

by.sTricky