10826 : 피보나치 수 4

원래 피보나치 수 5를 해결했었기 때문에 바로 코드를 집어 넣으니 런타임 에러가 발생했다.

그 이유는 python의 재귀 깊이의 default 값은 1000으로 설정되어 있다는 것.

처음으로 한 일은 재귀의 깊이를 풀어주는 일이었다.

(문제에서 요구하는 n은 10000까지였기 때문에 100000까지 제한을 늘려주었다.)
(이렇게 제한을 늘려도 너무 깊은 재귀는 실행되지 않는다고 했다.(정확하지 않음))

import sys
sys.setrecursionlimit(100000)
def fibonacci(first_num, second_num, count) :
    tmp = first_num + second_num
    count -= 1

    if (count > 0) :
        return fibonacci(first_num = second_num,second_num= tmp, count= count)

    else :
        return tmp

n = int(input())

first = 0
second = 1
if(n == 0) :
    print(0)
elif(n==1) :
    print(1)
else :
    result = fibonacci(first_num= first, second_num= second, count= n - 1)
    print(result)

결과는 메모리 초과가 발생했다.

두 번째로 시도한 일은 인터넷에서 찾은 동적 계획법이었다.

동적 계획법(Dynamic Programming)

: 쉽게 말해 큰 문제를 하위의 여러 가지 문제로 나누어 푸는 것이다.

더욱 더 이해하기 쉽게 말하면 한 문제는 단 한번만 풀 수 있게 만드는 것이다.

(특히 피보나치 수열에서 효과적이라고 한다.)
위의 피보나치 함수는 지수 형태의 시간복잡도를 가지고 있다. (약 2^n)

그렇기 때문에 어느 정도의 큰 수를 넣으면 프로그램이 튕겨버린다...

그래서 메모이제이션(Memoization)기법을 활용한다.

우리가 계산했던 fibonacci(2), fibonacci(3) ... 등의 함수를 불러와 다시 계산하지 않고,

계산했던 함수의 값을 임의의 공간에 저장해 그대로 다시 써 먹는 것이다.

그러면 함수를 호출해 다시 계산할 필요가 없으니 지수 형태였던 시간 복잡도를 O(N)으로 확연히 낮출 수 있다.

(fibonacci(10000)이면 딱 10000번만 계산해 저장된 값을 이용하면 된다!!)

# 재귀함수로는 메모리 초과, 시간 초과로 풀리지 않는다. 
# fibonacci의 10000 번째 수는 생각보다 훨씬 더 큰 수였다..
# 이런 식으로 정보를 저장하며 풀어나가는 것을 동적계획법(Dynamic Programming)이라고 했다.
def fibonacci(count) :
    first_num = 0
    second_num = 1

    for i in range(count) :
        first_num, second_num = second_num, (first_num + second_num)

    return first_num

n = int(input())

if(n == 0) :
    print(0)
elif(n==1) :
    print(1)
else :
    result = fibonacci(count= n)
    print(result)

이 코드로 10826: 피보나치 수 4의 문제를 해결했다!

동적 계획법의 개념인 '큰 문제를 작은 문제로 쪼개서 해결한다.' 라는 말은 자주 들어보았던 것 같은데 정작 어떻게 쪼개서, 어떤 방법으로 해결하는지에 대해서는 알지 못했다.

더 많은 문제를 풀어보고, 나에게 맞는 방법으로 익혀 나가야겠다.