In [1]:
def factorial(n):
if n <= 0:
return 1
else:
return n * factorial(n-1)
그런데 위 함수는 예를 들어 factorial(1000)을 계산하지 못하는 단점이 있는데,
이는 위 함수가 스택공간에서 사용하는 공간을 너무 많이 차지해서 결국은 RuntimeError를 발생시키기 때문이다.
실제로 factorial 함수를 1000번 호출하는데 이렇게 하면 메모리의 스택영역을 초과해버린다.
그렇다면 1000!를 실질적으로는 계산할 수 없다는 말인데 이건 좀 문제가 있다.
하지만 이 문제는 재귀를 사용하였기 때문에 발생하는 문제이다.
재귀를 사용하지 않으면서 팩토리얼을 계산하는 함수를 구현해 보자.
그러기 위해서는 앞서 구현한 factorial 함수의 입력값이 조금만 커지더라도 제대로 작동하지 못하는 이유를
알아내야 한다. 그래야 동일한 문제를 피하는 방식으로 메모리를 활용하는 코드를 구현할 수 있기 때문이다.
스택영역을 과부하시키지 않으면서 팩토리얼을 계산하는 코드를 아래와 같이 단순하게 구현할 수 있다.
In [2]:
def fact_for(n):
mult = 1
for i in range(n+1)[1:]:
mult = mult * i
return mult
fact_for를 이용하면 1000!을 매우 빠르게 계산하는 것을 확인할 수 있다.
In [3]:
fact_for(1000)
Out[3]:
참고로 1000!은 2568 자리수이다.
In [4]:
len(str(fact_for(1000)))
Out[4]:
심지어는 100000!(십만 팩토리얼)도 몇 초 내에 구한다.
하지만 1000000!(백만 팩토리얼)은 현재 사용하는 컴퓨터에서 3분을 기다려도 답을 주지 않았다.
아마 더 기다리면 답을 내긴 하겠지만 아마도 정확하지 않은 값이 나올 가능성이 매우 높다.
이유는 1000000!이 너무 큰 숫자라는 데에 있다.
100!은 120여자리수이고, 200!은 250여자리수, 등등 숫자의 자리수가 매우 빠르게 커진다.
쉽게 말해서 하나의 int형 숫자는 기본적으로 4 byte 공간에 들어가야 하는데 1000!은 4 byte
크기의 그릇에 들어가지 않는다는 말이다.
즉, 버퍼 오버런(buffer overrun)이 발생한다.
이제 문제의 본질을 알아 냈다.
따라서 숫자를 특별하게 처리하는 방법이 필요하다.
100!, 200! 등의 매우 큰 수를 다루는 방법 중의 하나는 리스트를 활용하는 것이다.
예를 들어 factorial(10) = 3628800인데 다음과 같이 길이가 7인 리스트에 역순으로 담을 수 있다.
list_fact(10) = [0, 0, 8, 8, 2, 6, 3]
물론 list_fact(10)은 factorial(10)과는 다르지만 list_fact(10)으로부터 factorial(10)을
구하는 일은 매우 쉬운 일이다:
factorial(10) = 0*1 + 0*1.0e+1 + 8*1.0e+2 + 8*1.0e+3 + 2*1.0e+4 + 6*1.0e+5 + 3*1.0e+6
처음 0은 1의 자리수, 둘째 0은 10의 자리수, 첫째 8은 100의 자리수, 둘째 8은 천의 자리수, 2는 만의 자리수, 6은 십만의 자리수, 마지막 3은 백만의 자리수 등등의 아이디어를 활용한 것이다. 이제 숫자를 역순으로 담는 이유를 이해할 수 있을 것이다. 즉, 자리수와 리스트의 인덱스가 정확하게 일치한다.
그런데 이 방식은 숫자가 웬만큼 커도 전혀 어렵지 않게 다를 수 있다.
예를 들어 500!의 경우 1135의 자리수인데 각 자리의 숫자를 길이가 1135인 리스트에 역순으로
하나의 숫자씩 담는 것이다.
각 자리의 숫자는 모두 0에서 9사이의 숫자이기 때문에 버퍼오버런 같은 일은 절대 방생하지 않으며,
또한 int형 정수만을 담은 길이가 1135인 리스트가 메모리 공간에서 차지하는 공간은
4540 byte = 1135 * 4 byte
즉, 4M 바이트에 불과하며, 이는 현대 컴퓨터에서 사용하는 메모리에 어떤 부담도 주지 않는 크기이다. 동영상 하나에 몇 기가에 비교해서 생각해보면 쉽게 이해될 것이다.
앞서 설명한 아이디어를 이용하여 아래 조건을 만족시키는 함수 list_fact를 구현하라.
list_fact는 정수 n을 입력받아 n! 해당하는 숫자들의 리스트를 리턴한다.예를 들어
list_fact(10) = '3628800'
이 성립해야 한다.
list_fact함수에 대응하는 C 언어 코드는 다음과 같다.
========
#include <stdio.h>
int fact[100000]={1};
int freq[11]={0};
int main()
{
int i,f,last = 1;
int mok,n;
scanf("%d",&n);
for( f = 1 ; f <= n; f++){
mok = 0;
for( i = 0 ; i < last ;i++){
fact[i] = fact[i]*f + mok;
mok = fact[i] / 10;
fact[i] = fact[i] % 10;
}
for( ; mok != 0 ; last++ ){
fact[last] = mok % 10;
mok /= 10;
}
}
In [5]:
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return (fibonacci(n-2) + fibonacci(n-1))
그런데 fibonacci 함수는 시간복잡도가 매우 크다. 인자로 양의 정수 n이 입력되면 2 ** n의 복잡도를 갖는다.
따라서 fibonacci(100)도 제대로 구하지 못한다.
시간복잡도 문제가 왜 발생하는지를 설명하라.
fibonacci(5) 함수가 호출될 때 메모리의 스택영역에서 발생하는 과정을 자세히 살펴 보아야 한다.
예를 들어 몇 번의 함수호출이 발생하고, 중복계산의 발생여부를 확인하라.
시간복잡도 문제를 해결하는 코드를 작성하라. 단, 코드는 재귀를 이용하는 방법과 아닌 방법 두 가지 모두 구현해야 한다.
피보나찌의 정의에 대해 좀 더 깊게 생각해본다.
예를 들어 fibonacci(5) 값을 구하기 위해 정말로 필요한 것은 무엇인지를 알아야 한다.
앞서의 문제에서 언급한 중복계산 문제를 해결해야 한다.
재귀를 이용할 경우 함수의 인자를 늘리는 것에 대해 생각해 볼 것.