[Python]파이썬으로 팩토리얼 구하기, 네 가지 방법

팩토리얼은 간단하게 n!로 나타내며,

 

1부터 n까지의 모든 자연수를 1씩 더해가며 곱하는 연산을 가리킨다.

 

개념을 더 정확하게 파악하려면 1부터 n까지의 자연수가 아닌 n부터 1까지의 자연수를 곱하는 게 맞지만,

 

지금은 그게 중요한게 아니니까.

 

파이썬으로는 크게 세 가지 방법으로 팩토리얼을 구현할 수 있다.

 

물론 바텀업 방식의 동적계획법 등은 여기에선 빠져있다.

 

가장 먼저, 파이썬의 math 라이브러리에서 제공하는 기본 함수를 사용하자.

 

그냥 가져다 쓰면 된다.

import sys
import math

n = int(sys.stdin.readline().rstrip())

print(math.factorial(n))

sys 라이브러리를 사용하지 않으면 세 줄로 팩토리얼 계산이 끝나버린다.

 

다음 방법은 재귀함수이다.

import sys


def fac(n):
    if n == 0:
        return 1
    return n * fac(n - 1)


n = int(sys.stdin.readline().rstrip())

print(fac(n))

재귀함수 문제를 풀어봤다면 한 번쯤은 구현해 봤을 법한, 팩토리얼 함수 구현이다.

 

다음으로는 반복문이다.

 

가장 직관적이면서 팩토리얼이 어떻게 계산되는지 이해하기 편하다.

import sys

n = int(sys.stdin.readline().rstrip())

result = 1
for i in range(1, n + 1):
    result *= i
print(result)

추가로, 기본 방법에서 제외했던 동적계획법을 이용하는 방법이다.

 

굳이 따지자면 시간복잡도와 공간복잡도는 재귀와 같지만, 계산 효율성이나 메모리 활용에서 이점이 있다.

 

구현은 아래와 같다.

import sys

n = int(sys.stdin.readline().rstrip())

memo = [1, 1] + [0] * (n - 1)

for i in range(2, n + 1):
    memo[i] = i * memo[i - 1]

print(memo[n])