[백준] 피보나치 함수

최동혁·2022년 12월 6일

baekjoon python 알고리즘

백준

목록 보기

38/68

피보나치 함수

solved_ac[Class3][피보나치 함수](https://www.acmicpc.net/problem/1003)

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 1

예제 출력 1

1 0
0 1
1 2

예제 입력 2

2
6
22

예제 출력 2

5 8
10946 17711

문제 해석

[백준]11050번: 이항 계수 1의 업그레이드 문제이다. dp를 이용해서 푸는 것인데, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하게끔 해서 수행 시간 효율성을 향상시킬수 있다.

11050번에 dp에 대해 자세한 설명이 있으니 참고하도록 하자.

풀이(dp 사용 x)

규칙

0 -> (1, 0)
1 -> (0, 1)
2 -> (1, 1)
3 -> (1, 2)
4 -> (2, 3)
5 -> (3, 5)
6 -> (5, 8)

숫자가 하나 증가할 때마다 1이 나오는 횟수가 1 증가한 숫자의 0이 나오는 횟수와 같아지며 1 증가한 숫자의 1이 나오는 횟수는 그 전 0이 나오는 횟수와 1이 나오는 횟수의 합과 같다.

무슨 얘기냐면 숫자 6의 값을 봐보자. 6은 5와 8을 출력하게 되는데 이는 5에서 (3, 5)에서 5가 6의 첫번째 숫자로 가고 3과 5의 합인 8은 숫자 6의 두번째 값인 8이 된다.

점화식 : list[i] = [list[i - 1][1], list[i - 1][0] + list[i - 1][1]]

0이 나오는 수를 입력해주는 배열과 1이 나오는 수를 입력해주는 배열을 따로 선언한다.
입력 받은 수가 0일때와 1일때는 직접 출력해준다.
왜냐면 초기 값을 주는 것이다.
그 외의 숫자가 입력되었을 때
- 계속해서 fibo_zero와 fibo_one은 업데이트가 된다. 여러개의 숫자를 입력받게 되면 그 전에 입력된 숫자에서 이미 한 연산을 다른 숫자가 입력되었다고 다시 할 필요가 없다. 그래서 fibo_zero의 길이까지는 이미 연산이 된 결과이기 때문에 연산이 되지 않은곳부터 시작한다. 그게 이 문제의 핵심이다.
  - 위의 점화식을 두개의 배열로 나누어서 각 배열에 넣어주었다.
  - 0이 나오는 수를 기록하는 fibo_zero[i]에는 그 전 숫자에서 1이 나오는 배열인 fibo_one[i - 1]을 넣어준다.
  - 1이 나오는 수를 기록하는 fibo_one[i]에는 그 전 숫자에서 1과 0이 나오는 수의 합을 넣어준다.

import sys

T = int(sys.stdin.readline())

fibo_zero = [1, 0]
fibo_one = [0, 1]

for i in range(T):
    a = int(sys.stdin.readline())
    if a == 0:
        print("1 0")
        continue
    elif a == 1:
        print("0 1")
        continue
    else:
        for i in range(len(fibo_zero), a + 1):
            fibo_zero.append(fibo_one[i - 1])
            fibo_one.append(fibo_zero[i - 1] + fibo_one[i - 1])
    print(fibo_zero[a], fibo_one[a])

풀이(dp 사용)

점화식 : list[i] = [list[i - 1][1], list[i - 1][0] + list[i - 1][1]]

최대 숫자는 40이라고 하였기 때문에 41까지 0,0으로 초기화를 해준다.
숫자 0과 1을 넣었을 때 나오는 값을 초기값으로 설정해준다.
dp 함수 선언
- 입력 받은 수가 0이거나 1이거나 dp에 이미 연산이 끝난 숫자라면?
  - d[x]를 그대로 return 해준다.
- 그게 아닌 새로운 숫자가 들어왔다면?
  - 전 숫자에서의 dp 값을 끌고와야 되기 때문에 dp(x - 1)을 호출하여 a라는 변수에 저장해준다.
  - 그렇다면 a[0]에는 (x - 1)에서 0이 나오는 수가 들어가있고, a[1]에는 1이 나오는 수가 들어가있을 것이다.
  - 위의 점화식대로 dp를 업데이트 해주고 return 해준다.

import sys

T = int(sys.stdin.readline())

d = [[0, 0] for _ in range(41)] 

d[0][0] = 1
d[0][1] = 0
d[1][0] = 0
d[1][1] = 1

def dp(x):
    if x == 0 or x == 1 or d[x][0] != 0:
        return d[x]
    else:
        a = dp(x - 1)
        d[x][0] = a[1]
        d[x][1] = a[0] + a[1]
    return d[x]

for i in range(T):
    a = int(sys.stdin.readline())
    dp(a)
    print(d[a][0], d[a][1])

시행착오

dp 테이블을 [[0, 0] for _ in range(41)]로 초기화 하는 것이 아닌 [0] * 41로 초기화를 해주고 2차원 배열로 사용하였다. 그랬더니 TypeError가 떴다. 답을 출력하는데는 문제가 없지만 1차원으로 초기화를 하고 2차원으로 사용을 하니 타입에러가 뜬것 같아서 다시 2차원으로 초기화를 해주었다. 첫번째로 푼 풀이도 어떻게 보면 dp를 사용한게 아닌가 싶다. 이미 연산을 끝낸 테이블은 값을 이용하여 같은 연산을 하지 않고 진행을 했다는 점에서 dp와 유사하지만 두 코드의 다른점은 첫번째 코드는 바텀업 방식을 이용하였고 두번째 코드는 탑다운 방식을 이용하여 풀었다는 것이다.