[BOJ]1003번, 피보나치 함수(Python)

1003번: 피보나치 함수

서론

 2년 전, 코린이 시절, 알고리즘 역량을 키우고 싶어서 무턱대고 백준에 아무 문제나 찾아서 풀었던 시절이 있었다. 그때는 solved.ac이 뭔지 티어가 뭔지도 몰랐던 시절이라 제목이 익숙했던 문제 하나를 뽑아 풀었다.

  피보나치 함수는 고등학교 수학에서 수열 배울때 많이 보던거이기도 하고 재귀함수를 그때 마침 학교에서 배울 때라 쉬울 거라 생각했지만, 이중for 문으로 별찍기도 어려워 하던 내게 이 문제는 재앙이었다.   

그때 느꼈던 감정을 Notion에 적었는데 정리해서 블로그로 올려보도록 하겠다.

문제

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);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

해설

 사실 이 문제의 핵심은 피보나치 함수의 이론이 아니라 피보나치 수열의 재귀 함수에서 f(0),f(1)이 몇 번이나 호출 되는가를 알아내는 것이다.

f(2)는 f(1)을 1번, f(0)을 1번 호출한다.

f(3)은 f(2)를 1번, f(1)을 1번 호출한다. 따라서 f(2)각 f(1)과 f(0)을 각각 1번씩 호출하기 때문에 총 f(1) 2번 f(0) 1번 을 호출한다. 그리고 이를 계속 나열해 보자

0  # n에 0을 넣었을때 
1 0 #  첫번째 값은 0이 나온 갯수 두번째 값은 1이 나온 갯수
1  # n에 1을 넣었을때
0 1
2   # n에 2을 넣었을때
1 1
3  # n에 3을 넣었을때
1 2
4  # n에 4을 넣었을때
2 3
5   # n에 5을 넣었을때
3 5
6   # n에 6을 넣었을때
5 8
7  # n에 7을 넣었을때
8 13
8  # n에 8을 넣었을때
13 21
9  # n에 9을 넣었을때
21 34
10  # n에 10을 넣었을때
34 55

피보나치 함수의 매개변수를 3이상으로 출력 했을때, 결과 값이 일종의 피보나치 수열 처럼 나오는걸 알 수 있었다.

하지만 피보나치 함수를 그대로 쓰면 시간초과 에러가 나고 재귀함수를 쓰면 계속 재귀적인 연산이 지속되고 스택 메모리를 많이 잡아먹기 때문에 리스트를 이용해서 해결했다.

f0=[1,0,1]
f1=[0,1,1]

def fibo(n):
    l=len(f0)
    if l<=n:
        for i in range(l,n+1):
            f0.append(f0[i-1]+f0[i-2])
            f1.append(f1[i-1]+f1[i-2])
    print(f0[n],f1[n])
for i in range(int(input())):
    fibo(int(input()))

초반에 3 이전에 호출되는 것, n-1, n-2를 얻기 위해 위와 같이 초기화를 해주고 그 후로는 피보나치 수열 처럼 진행되기 때문에 리스트에  원하는 n값까지 계속 for문을 통해 구해주고 for문이 끝난 뒤
n에 해당하는 배열의 인덱스에 값을 출력한다. 

초반에 접근을 잘못해서 시간을 많이 썼지만 본질을 이해하면 쉬운 문제였다