[Python] 백준 알고리즘 1003번 : 피보나치 함수, DP문제

이번에 푸는 문제는 백준 알고리즘 1003번 : 피보나치 함수로 난이도는 Siver 3 에 해당한다. (solve.ac 기준)

문제는 다음과 같다.

피보나치 함수는

fibonacci(0) = 1*fibonacci(0) + 0*fibonacci(1) = > 0과 1의 총 호출 횟수 = 1

fibonacci(1) = 0*fibonacci(0) + 1*fibonacci(1) = > 0과 1의 총 호출 횟수 = 1

로 시작하며, 그 뒤는 호출이 반복이 되는 재귀함수이다.

 

fibonacci(2) = (1+0)*fibonacci(0) + (0+1)*fibonacci(1) = > 0과 1의 총 호출 횟수 = 2

fibonacci(3) = fibonacci(1) + fibonacci(2) = 0*fibonacci(0) + 1*fibonacci(1) + 1*fibonacci(0) + 1*fibonacci(1)

                = (0+1)*fibonacci(0) + (1+1)*fibonacci(1) = > 0과 1의 총 호출 횟수 = 3

fibonacci(4) = fibonacci(2) + fibonacci(3) = 1*fibonacci(0) + 1*fibonacci(1) + 1*fibonacci(0) + 2*fibonacci(1)

                = (1+1)*fibonacci(0) + (1+2)*fibonacci(1) = > 0과 1의 총 호출 횟수 = 5

fibonacci(5) = fibonacci(3) + fibonacci(4) = 1*fibonacci(0) + 2*fibonacci(1) + 2*fibonacci(0) + 3*fibonacci(1)

                = (1+2)*fibonacci(0) + (2+3)*fibonacci(1) = > 0과 1의 총 호출 횟수 = 8

fibonacci(6) = fibonacci(4) + fibonacci(5) = 2*fibonacci(0) + 3*fibonacci(1) +3*fibonacci(0) + 5*fibonacci(1)

                = (2+3)*fibonacci(0) + (3+5)*fibonacci(1) = > 0과 1의 총 호출 횟수 = 13

fibonacci(7) = fibonacci(3) + fibonacci(4) = 1*fibonacci(0) + 2*fibonacci(1) + 2*fibonacci(0) + 3*fibonacci(1)

                = (3+5)*fibonacci(0) + (5+8)*fibonacci(1) = > 0과 1의 총 호출 횟수 = 21

.

.

.

이처럼 진행될 것이며, 다음 색에 표시한 것과 같이 각 숫자가 어디에서 왔는지 알 수 있다.

결국 fibonacci(n) 의 0 호출 횟수는 fibonacci(n-2)와 같고, 1 호출 횟수는 fibonacci(n-1)과 같음을 알 수 있다.

 

그리고, 재귀의 depth를 적게하기위해서는 메모이제이션(진행사항을 저장하면서 나아가는 것)을 사용하는게 좋다.

 

# 2020-07-18 1st
# 2020-12-22 review
# 알고리즘 - DP
# 문제번호 : 1003
# 메모이제이션 활용

# 0 ~ 40 까지의 정수
fibolist = [0]*41

def fibonacci(n):
    if(n == 0):
        fibolist[0] = 0
        return 0
    elif(n == 1):
        fibolist[1] = 1
        return 1
    else:
        # 값이 존재한다면 이용
        if(fibolist[n]!=0):
            return fibolist[n]
        else:
            # 값이 없으면 갱신
            fibolist[n] = fibonacci(n-1) + fibonacci(n-2)
            return fibolist[n]

# test 횟수
testcase = int(input())

for i in range(testcase):
    test = int(input())
    if(test == 0):
        print("1 0")
    elif(test == 1):
        print("0 1")
    else:
        fibonacci(test)
        print(str(fibolist[test-1])+" "+str(fibolist[test]))

 

 

문제는 아래 ↓링크↓

1003번: 피보나치 함수