<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 연습문제
아래 문제들을 해결하는 코드를 lab09.py 파일에 작성하여 제출하라.
단, 코드가 아닌 문제는 주석처리를 한다.
여러 줄에 걸친 주석은 
Step2:  그런데 위 함수는 예를 들어 factorial(1000)을 계산하지 못하는 단점이 있는데, 
이는 위 함수가 스택공간에서 사용하는 공간을 너무 많이 차지해서 결국은 RuntimeError를 발생시키기 때문이다.
실제로 factorial 함수를 1000번 호출하는데 이렇게 하면 메모리의 스택영역을 초과해버린다.
그렇다면 1000!를 실질적으로는 계산할 수 없다는 말인데 이건 좀 문제가 있다.
하지만 이 문제는 재귀를 사용하였기 때문에 발생하는 문제이다. 
재귀를 사용하지 않으면서 팩토리얼을 계산하는 함수를 구현해 보자.
그러기 위해서는 앞서 구현한 factorial 함수의 입력값이 조금만 커지더라도 제대로 작동하지 못하는 이유를 
알아내야 한다. 그래야 동일한 문제를 피하는 방식으로 메모리를 활용하는 코드를 구현할 수 있기 때문이다.
스택영역을 과부하시키지 않으면서 팩토리얼을 계산하는 코드를 아래와 같이 단순하게 구현할 수 있다.
Step3:  fact_for를 이용하면 1000!을 매우 빠르게 계산하는 것을 확인할 수 있다.
Step4:  참고로 1000!은 2568 자리수이다.
Step5:  심지어는 100000!(십만 팩토리얼)도 몇 초 내에 구한다. 
하지만 1000000!(백만 팩토리얼)은 현재 사용하는 컴퓨터에서 3분을 기다려도 답을 주지 않았다.
아마 더 기다리면 답을 내긴 하겠지만 아마도 정확하지 않은 값이 나올 가능성이 매우 높다.
이유는 1000000!이 너무 큰 숫자라는 데에 있다. 
100!은 120여자리수이고, 200!은 250여자리수, 등등 숫자의 자리수가 매우 빠르게 커진다.
쉽게 말해서 하나의 int형 숫자는 기본적으로 4 byte 공간에 들어가야 하는데 1000!은 4 byte 
크기의 그릇에 들어가지 않는다는 말이다. 
즉, 버퍼 오버런(buffer overrun)이 발생한다.
이제 문제의 본질을 알아 냈다. 
첫째, 재귀를 사용하면 스택영역에 과부하가 걸리고
둘째, for 문을 사용하면 컴퓨터가 일반적으로 숫자를 처리하는 방식으로는 제대로 된 값을 얻을 수 없다.  
따라서 숫자를 특별하게 처리하는 방법이 필요하다.
매우 큰 수의 연산
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)을 
구하는 일은 매우 쉬운 일이다
<ASSISTANT_TASK:>
Python Code:
def factorial(n):
    if n <= 0:
        return 1
    else: 
        return n * factorial(n-1)
Explanation: 연습문제
아래 문제들을 해결하는 코드를 lab09.py 파일에 작성하여 제출하라.
단, 코드가 아닌 문제는 주석처리를 한다.
여러 줄에 걸친 주석은  ... 를 활용하면 된다.
재귀함수
팩토리얼 함수
팩토리얼 함수를 아래와 같이 재귀를 이용하여 매우 간단하게 구현할 수 있다.
End of explanation
def fact_for(n):
    mult = 1
    for i in range(n+1)[1:]:
        mult = mult * i
    return mult
Explanation: 그런데 위 함수는 예를 들어 factorial(1000)을 계산하지 못하는 단점이 있는데, 
이는 위 함수가 스택공간에서 사용하는 공간을 너무 많이 차지해서 결국은 RuntimeError를 발생시키기 때문이다.
실제로 factorial 함수를 1000번 호출하는데 이렇게 하면 메모리의 스택영역을 초과해버린다.
그렇다면 1000!를 실질적으로는 계산할 수 없다는 말인데 이건 좀 문제가 있다.
하지만 이 문제는 재귀를 사용하였기 때문에 발생하는 문제이다. 
재귀를 사용하지 않으면서 팩토리얼을 계산하는 함수를 구현해 보자.
그러기 위해서는 앞서 구현한 factorial 함수의 입력값이 조금만 커지더라도 제대로 작동하지 못하는 이유를 
알아내야 한다. 그래야 동일한 문제를 피하는 방식으로 메모리를 활용하는 코드를 구현할 수 있기 때문이다.
스택영역을 과부하시키지 않으면서 팩토리얼을 계산하는 코드를 아래와 같이 단순하게 구현할 수 있다.
End of explanation
fact_for(1000)
Explanation: fact_for를 이용하면 1000!을 매우 빠르게 계산하는 것을 확인할 수 있다.
End of explanation
len(str(fact_for(1000)))
Explanation: 참고로 1000!은 2568 자리수이다.
End of explanation
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return (fibonacci(n-2) + fibonacci(n-1))
Explanation: 심지어는 100000!(십만 팩토리얼)도 몇 초 내에 구한다. 
하지만 1000000!(백만 팩토리얼)은 현재 사용하는 컴퓨터에서 3분을 기다려도 답을 주지 않았다.
아마 더 기다리면 답을 내긴 하겠지만 아마도 정확하지 않은 값이 나올 가능성이 매우 높다.
이유는 1000000!이 너무 큰 숫자라는 데에 있다. 
100!은 120여자리수이고, 200!은 250여자리수, 등등 숫자의 자리수가 매우 빠르게 커진다.
쉽게 말해서 하나의 int형 숫자는 기본적으로 4 byte 공간에 들어가야 하는데 1000!은 4 byte 
크기의 그릇에 들어가지 않는다는 말이다. 
즉, 버퍼 오버런(buffer overrun)이 발생한다.
이제 문제의 본질을 알아 냈다. 
첫째, 재귀를 사용하면 스택영역에 과부하가 걸리고
둘째, for 문을 사용하면 컴퓨터가 일반적으로 숫자를 처리하는 방식으로는 제대로 된 값을 얻을 수 없다.  
따라서 숫자를 특별하게 처리하는 방법이 필요하다.
매우 큰 수의 연산
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 &lt;stdio.h&gt;
int fact[100000]={1}; 
int freq[11]={0};
int main() 
{
    int i,f,last = 1; 
    int mok,n;
    scanf("%d",&amp;n);
    for( f = 1 ; f &lt;= n; f++){ 
    mok = 0;
    for( i = 0 ; i &lt; 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;
    } 
}
피보나찌 수열
n번 째 피보나찌 값을 구하는 함수를 아래와 같이 재귀를 이용하여 간단하게 구현할 수 있다.
End of explanation
<END_TASK>