본문 바로가기
Computer Engineering/백준

[백준/파이썬3/1003] 피보나치 함수

by UC우공 2020. 1. 10.

피보나치 함수

문제

다음 소스는 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이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력

예제 출력

   3  
   0    1   0
   1    0   1
   3    1   2

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
= int(input())
 
for j in range (0, T):
    A = int(input()) 
    val = [01
    if A==0:
        print(1,0)
    elif A==1:
        print(0,1
    elif A==2:
        print(1,1
    else:
        for i in range(2, A+1):
            val.append(val[i-1+ val[i-2]) 
        print(val[A-1],val[A])
 

우선 본문에서 보여준 C++는 탑다운(Top-Down) 방식으로 엄청난 양의 메모리를 사용하게 될 수도 있다.

우선 풀이에 주어진 제한시간이 0.25초 이므로 연산횟수도 줄이고 메모리도 줄이는 방식으로 for문을 통한 바텀업(Botton-Up)을 사용해야한다.

 

풀이가 이해가 잘 가지 않는다면 이전에 게재했던 DP에 관련해서 읽어보는 걸 추천한다.

 

 

 

Dynamic programming 동적 계획법

엄청 예전에 프로그래밍 수업을 들을때 피보나치 수열 값 표시하면서 분명히 들어본거 같은데, 그 당시만해도 딱히 프로그래밍에 관심이 없어서 당시에는 아 이런게 있구나하고 넘어갔지만, 이제서야 동적계획의 D..

woogong2.tistory.com

댓글