[코딩테스트]백준 - 피보나치 함수(1003번)

Adela·2020년 7월 27일
0

백준온라인저지

목록 보기
37/53
post-thumbnail

피보나치 함수

문제

다음 소스는 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

3
0
1
3

예제 출력 1

1 0
0 1
1 2

출처

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: cyj101366
  • 데이터를 추가한 사람: doju wonrok97

알고리즘 분류

  • 다이나믹 프로그래밍

해결한 코드

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split('\n');
var t = input[0] / 1
var ns = []
for (var i = 1; i < input.length; i++) {
    ns.push(input[i]/1)
}

var dp = []
dp[0] = [1, 0]
dp[1] = [0, 1]
for (var idx = 2; idx < 41; idx++) {
    dp[idx] = [(dp[idx - 1][0] + dp[idx - 2][0]), (dp[idx - 1][1] + dp[idx - 2][1])]
}

var n = ''
for(var i=0; i<ns.length; i++){
    n += dp[ns[i]].join(' ') + '\n'
}

console.log(n)

알고리즘

1. 점화식을 만든다.

※ 이를 위해 피보나치 함수가 돌아가는 방식을 이해한다.

  • fibonacci(3)의 경우
    • return fibonacci(2)를 부른다.
    • return fibonacci(1)을 부른다. 👈🏻 이 때 1을 출력한다.
    • fibonacci(2)return fibonacci(1)return fibonacci(0)을 부른다.
      👉🏻 이 때 1과 0을 출력한다.

fibonacci(3)fibonacci(2)fibonacci(1) 결과의 합이다.
규칙을 발견하였으니 이제 다이나믹 프로그래밍을 구현한다.

2. 결과를 메모할 dp 배열을 만든다.

dp = []

피보나치 함수에 0을 넣으면 바로 return 0이 되므로,

dp[0] = [1, 0]

피보나치 함수에 1을 넣으면 바로 return 1이 되므로,

dp[1] = [0, 1]

피보나치 함수에 2를 넣으면,
fibonacci(1)fibonacci(0)을 부르니까, dp[0]dp[1]에 저장된 각 값의 합만큼 0과 1이 출력된다.
👉🏻 따라서 2 이상 ~ 40 이하의 숫자들에 대한 값을 dp 배열에 저장한다.

3. 테스트케이스의 숫자들에 대한 값을 출력한다.

나는 (혹시나 모를) 시간초과를 막기 위해 값들을 모두 문자열로 만들어 한번에 출력했다.

profile
개발 공부하는 심리학도

0개의 댓글