[Python] 백준1003 피보나치 함수

31 Dec 2022 in Study on Algorithm

백준1003 피보나치 함수 링크

문제

예제 입력

---

코드

import sys
t = int(input())

for _ in range(t):
    num = int(sys.stdin.readline())
    zeroCnt = [1, 0]
    oneCnt = [0, 1]
    for _ in range(2, num+1):
        zeroCnt.append(zeroCnt[-2] + zeroCnt[-1])
        oneCnt.append(oneCnt[-2] + oneCnt[-1])    
    print(zeroCnt[num], oneCnt[num])

설명

파이썬을 통해서 사용자로부터 입력받아 조건문/반복문을 사용하여 피보나치 함수을 구현했습니다.

---

정리

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");                                    
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

def fibonacci(n) :
    global zeroCnt
    global oneCnt
    if n == 0 :
        zeroCnt += 1
        return 0
    elif n == 1 :
        oneCnt += 1
        return 1
    else :
        return fibonacci(n-1) + fibonacci(n-2)

처음 문제를 봤을 때는 해당 함수를 사용하여 문제를 푸는 것인 줄 알고 제출했다가 시간 초과가 발생했습니다. 피보나치 수열을 구현하는데 두 가지 방법으로 함수를 이용한 재귀함수와 다이나믹 알고리즘(동적계획)을 이용한 반복문으로 해결하는 것이 있습니다. dp로 반복적인 패턴을 찾아 저장하고 그것을 다시 재사용하여 다른 값을 구하는 방식으로 재귀함수보다 빠른 성능을 가지게 됩니다.

---

결과