백준 1003 피보나치 함수, 다이나믹 프로그래밍 DP (with 파이썬)

피보나치 수열 알고리즘 문제 풀이

▶ 백준 문제풀이 1003

https://www.acmicpc.net/problem/1003

피보나치 수열이란

• 연속한 두 수의 합이 그다음 수가 되는 수열
  {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... }
• 재귀적으로 표현 가능
  Fn = Fn-1 + Fn-2 또는 Fn+1 = Fn + Fn-1
  단, F0 = 0, F1 = 1
• 참고 사이트

피보나치 수열

다이나믹 프로그램이란

• 답을 재활용 하는 방법
  앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하고...
  엄밀히 말해 동적 계획법은 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다.
• 이미 구했던 값은 메모리에 담아두고 필요시 메모리에서 값을 가져옴.
  재계산, 재호출 하지 않는다.
• 참고 사이트

동적 계획법

풀이

다이나믹 프로그래밍 방법으로 풀어야 시간초과를 넘길 수 있다.

문제에 기재되어 있는 코드로 진행하면 시간초과 발생

"""
https://www.acmicpc.net/problem/1003
"""
#시간초과 발생
import sys
T = int(sys.stdin.readline().rstrip())
N = [int(input()) for _ in range(0, T)]

def fibonacci(no):
    if (no == 0):        
        return 0
    elif (no == 1):        
        return 1
    else:
        return fibonacci(no-1) + fibonacci(no-2)
    
for i in range(0, T):
    if N[i] == 0:
        print("1 0") #0인 경우, 초기값 리턴
    else:
        print(str(fibonacci(N[i]-1)) + " " + str(fibonacci(N[i])))
"""
2
6
22
5 8
10946 17711
"""

 

다이나믹 프로그래밍 방법으로 코딩

• 재귀호출 시, 한번 호출된 값을 리스트에 저장하여 재활용한다.

import sys
T = int(sys.stdin.readline().rstrip())
N = [int(input()) for _ in range(0, T)]

#다이나믹 프로그래밍 적용. 한번 호출된 값은 메모리에 저장. 재호출 안함
def fibonacci(no):
    #매개변수 만큼 0으로 세팅한 리스트 생성
    dnmlst = [0 for _ in range(0,no+1)] 
    dnmlst[0] = 0 # 리스트에 피보나치 수열 0 초기값 세팅
    if (no == 0):
        return "1 0" #매개변수 0인 경우, 초기값 리턴
    elif (no > 0):
        dnmlst[1] = 1 # 리스트에 피보나치 수열 1 초기값 세팅

    #반복문 사용
    for i in range(2, no+1):        
        #저장된 이전값으로 재귀호출
        dnmlst[i] = int(dnmlst[i-1]) + int(dnmlst[i-2])                    
    result = str(dnmlst[no-1]) + " " + str(dnmlst[no])
    return result

for i in range(0, T):
    print(fibonacci(N[i]))
"""
2
6
22
5 8
10946 17711
"""