[Python] BOJ 2748 : 피보나치 수 2

요구사항

1. 시간 제한 1초 
   1. N이 90이하 이므로 O(N^3) 까지 가능할 것. 
2. 메모리 제한 128MB 
   1. N이 매우 작으니 신경 안 써도 될 것.
3. N이 주어질 때, N번 째 피보나치 수를 출력한다.
   1. ex) N = 3이면, 0,1,1 -< 1을 출력.

설계

위 문제는 주관적인 생각으론 3가지 방법으로 풀어보고 싶다. 

1. 재귀함수
   1. 사용자 정의 함수 안의 base case 설정 : N = 1일때 0을 N = 2일 때 1을 출력할 수 있게 한다.
   2. 그 외 return 함수(N-1) + 함수(N-2) 를 할 수 있도록 한다.  
2. Top-Down
   1. 위 방식은 큰 문제를 작은 단위의 문제로 나누어 쪼개는 동적계획법 알고리즘 설계 방법 중 하나이다. 
   2. 동적 계획법 즉, DP는 메모제이션을 사용한다. 메모제이션이란,,, 냉장고라고 생각하면 된다. 마트까지 가지 않고 원하는 값을 냉장고에서 꺼내 먹는... 비유는 잊으세요...
   3. 저장할 리스트를 N개만큼 초기화 해준다.
   4. 사용자 정의 함수를 돌린 결과값을 초기화 해준 리스트에 저장해준다. 
   5. 그 외는 재귀 함수의 설계와 비슷합니다. 아래 구현에서 봬요. 
3. Bottom-Up
   1. 위 방식은 큰 문제를 풀긴 하는 데 작은 문제부터 해결해 큰 문제를 해결하는 방식 이라고 생각하면 편하다.
   2. 결과값을 저장할 리스트를 초기화해준다. 
   3. base case 를 설정해준다.
   4. for문을 이용해 해결한다. 

구현

1. 재귀함수 

def fibo(N):
    if N == 1:
        return 0
    elif N == 2:
        return 1
    else:
        return fibo(N-1) + fibo(N-2)

print(fibo(int(input()))

실수?

1. 0번 째 피보나치 수는 0이다. ㅋㅋㅋ 1 번 째가 아니라 ㅠㅠ
2. 따라서 아래와 같이 수정해줘야 한다.

def fibo(N):
    if N == 0:
        return 0
    elif N == 1:
        return 1
    else:
        return fibo(N-1) + fibo(N-2)

print(fibo(int(input())))

• 백준에서 위 소스 코드는 시간 초과가 난다. 
• 그 이유는 아래와 같다.

fibo(5)
└── fibo(4)
    └── fibo(3)
        └── fibo(2)
        └── fibo(1)
    └── fibo(2)
└── fibo(3)
    └── fibo(2)
    └── fibo(1)

• 피보나치 수열의 계산의 시간 복잡도가 O(2^N) 이므로 초반 요구사항인 O(N^3)을 만족하지 못하기 때문이다. 
• 따라서 방식 2, 3번으로 문제를 제출하면 되겠다. 

2. Top-Down

def fibo(N):
    if N == 0:
        return 0
    elif N == 1:
        return 1
    
    if dp[N] != 0:
        return dp[N]
    
    dp[N] = fibo(N-1) + fibo(N-2)

    return dp[N]

N = int(input())
dp = [0] * (N+1)
print(fibo(N))

• 1번 재귀 함수로 풀 경우 같은 값을 반복해서 계산한다. 예를 들어 fibo(5)를 계산할 때, fibo(4)와 fibo(3) 을 계산한다. 근데 fibo(4)를 계산하려면 fibo(3)과 fibo(2)를 다시 계산한다. 즉, 같은 피보나치 값을 여러 번 중복으로 계산하게 된다.
• 하지만 top-down 방식으로 피보나치 수열을 계산 하면, 메모리에 값을 저장해 중복을 막아준다.
• 그래서 시간 복잡도 O(N)을 갖는다.

3. Down-Up

N = int(input())

dp = [0] * (N+1)
dp[0] = 0
dp[1] = 1

for i in range(2, N+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[N])

• 여기서 for문이 2부터 시작하는 건, dp의 0과 1에 대한 basecase를 설정해주었기 때문이다.