BOJ 10872번 : 팩토리얼

안녕하세요. 지난 포스팅의 BOJ 9020번 : 골드바흐의 추측에서는 기본 수학 2 카테고리의 마지막 문제로 소수와 관련된 문제를 풀어보았습니다. 핵심은 반복적인 소수 검정 이였습니다. 오늘부터는 수학적인 지식보다는 컴퓨터공학적 지식이 더욱 필요한 재귀함수와 관련된 문제를 풀어보도록 하겠습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 재귀 함수의 정의
• 팩토리얼의 정의

 

제출 코드

def factorial(N) :
    if N == 1 or N == 0 : return 1
    else : return N * factorial(N - 1)

print(factorial(int(input())))

 

해설

기본적으로 재귀함수(recursive function)이란 함수 내에서 함수를 호출하는 함수 구조를 의미합니다. 대표적으로 위의 팩토리얼을 계산할 때 적용해볼 수 있습니다. 이를 위해서 팩토리얼이 무엇인지 알아보면 $N$이 주어졌을 때 $N$과 같거나 작은 모든 자연수들의 곱을 의미합니다. 

 

$$N! = N \times (N - 1) \times (N - 2) \times \cdots \times 3 \times 2 \times 1$$

 

팩토리얼의 정의만 알았다면 재귀함수를 이용해서 문제를 쉽게 풀 수 있습니다. 재귀함수를 사용한다는 것은 방금 전에도 설명드렸다 싶이 함수 내에서 함수를 호출하는 구조를 의미합니다. 이 정의는 컴퓨터공학적 정의이고 이를 저희가 알고 있는 수학적 정의로 바꾸어보면 어떻게 쓸 수 있을까요? 바로 점화식(recursion formula)입니다. 점화식도 재귀함수와 마찬가지로 어떤 수열의 일반항으로 이루어진 식을 의미합니다. 위 팩토리얼 함수를 예로 들어서 설명해보도록 하죠. 

 

$$a_{n} = n!$$

 

위와 같이 정의하면 단순히 팩토리얼의 일반항이 입니다. 그렇다면 $n! = n \times (n - 1)!$임을 이용하면 아래와 같이 쓸 수 있겠죠?

 

$$a_{n} = n \times (n - 1)! = na_{n - 1}$$

 

이와 같은 구조를 가진 식을 점화식이라고 합니다. 이는 오늘 알아볼 재귀함수와 나중에 알아볼 동적 프로그래밍(Dynamic Programming)에서 아주 중요한 개념이기 때문에 꼭 알아두셔야합니다. 자, 위 점화식을 재귀함수 형태로 만들어보도록 하죠. $f(n) = n!$로 정의된 함수라고 가정하면 재귀함수 형태로 쓸 수 있습니다. 

 

$$f(n) = nf(n - 1)$$

 

위와 같은 재귀함수에서 중요한 것은 종료조건(terminal condition)입니다. 반복문과 마찬가지로 종료조건이 명시되어 있지 않으면 재귀함수는 일반적으로 무한정으로 함수를 호출하게 되고 이는 메모리가 터지는 현상인 스택 오버 플로우(stack over flow)를 맞이하게 됩니다. 종료조건은 문제마다 다르기 때문에 문제를 잘 이해하셔야합니다. 일반적으로 팩토리얼은 $0! = 1! = 1$이기 때문에 종료조건으로 $N = 1$ 또는 $N= 0$이면 1을 반환하도록 함수를 만들어주면 되겠네요. 그렇지 않을 때는 N * factorial(N - 1)을 반환해서 팩토리얼을 계속 계산해주면 됩니다. 

 

참고자료 및 그림출처

백준 코딩 문제