[알고리즘_문제] 백준 1003 | 피보나치 함수

 

---

 

 

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

 

 

 

접근 방법

기존과 같은 재귀 방식으로 풀면 시간 초과가 나는 유형이다. (제한시간 0.25초)

 

먼저 재귀함수를 작성해보자.

 

let n = 10;

function fibonachi(n) {
	if (n <= 1) return n;
	return fibonachi(n - 1) + fibonachi(n - 2);
}

console.log(fibonachi(n))

 

이건 재귀라 시간이 너무 오래 걸린다. O(n2)나 걸리니... 다른 방법으로 해보자.

 

Down-Top (반복문) + 메모이제이션 방식이다.

 

메모이제이션(Memoization)이란?

문제를 한번 풀면 이걸 배열에 저장해서 다음 문제를 풀 때 가져온다. 라는 개념이다.

* 메모이제이션은 재귀함수에서도 적용이 가능하다.

 

let n = 10;

function fibonachi(n) {
	const T = [0, 1]
	for (let i = 2; i <= n; i++) {
		T[i] = T[i - 1] + T[i - 2]
	}

	return T[n];
}

console.log(fibonachi(n))

 

이렇게 짜면 stack에서 함수가 빠르게 빠지고 바로 다음 계산을 할 수 있어 상대적으로 굉장히 빠른 속도로 계산을 마치게 된다. 그리고  T라는 공간에 결과값을 넣어두고 다음 계산식에서 저장된 값을 빠르게 가져오니 더 빠른 계산이 된다.

 

출처 : velog.io/@polynomeer/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

동적 계획법(Dynamic Programming)

 

백준 문제에 적용해보자.

 

---

 

/* Simple Hello World in Node.js */
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let count = 0;
let incount = 0;

rl.on("line", function (line) {
    const T = parseInt(line);
    fibonachi(T);
});

function fibonachi(T) {
    if (count === 0) {
        count = T;
        return;
    }
    else {
        incount++;
        // 내용입력
       

        if (count === incount) {
            rl.close();
        }
    }
}

 

테스트용 코드다 저렇게 하면 처음 입력시 입력값을 받은대로 입력받게 되고 자동으로 종료된다.

 

다음은 DOWN TOP + 메모이제이션 방식이다.

 

/* Simple Hello World in Node.js */
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let count = 0;
let incount = 0;

rl.on("line", function (line) {
    const T = parseInt(line);
    fibonachi(T);
});

function fibonachi(T) {
    if (count === 0) {
        count = T;
        return;
    }
    else {
        incount++;
        // 내용입력
        let dp = [0, 1]
        if (T === 0) {
            console.log("1 0");
        } else if (T === 1) {
            console.log("0 1")
        } else {
            for (let i = 2; i <= T; i++) {
                dp[i] = dp[i - 1] + dp[i - 2]
            }

            const result = dp[T - 1] + " " + dp[T]
            console.log(result)
        }

        if (count === incount) {
            rl.close();
        }
    }
}

 

 

이미 0과 1이 들어갈 경우의 답은 알고 있으니 하드코딩으로 넣어준다. 0,1 1,0

 

N이 주어졌을 때 fibonachi(n)을 호출햇을 때, 0과 1이 각각 몇 번 호출하는지를 구하는 문제다.

피보나치를 통해 얻을 수 있는 0과 1의 각 개수를 구하면 된다.

 

1의 경우에는 결과의 가장 마지막 배열값이 된다.

예를 들어 n이 3이면 결과가 2가 된다.

 

0의 의 개수는 n-1로 정할 수 있다.

 

문제를 제대로 이해 했는지 나 자신에게 물어봤더니 아니라고 한다 ㅠ;;

 

다음은 재귀 메모화 코드이다. 도움을 받아 풀었다... 허허

 

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

let count = 0;
let incount = 0;
let dp = new Array();

rl.on('line', function (line) {

    let num = parseInt(line);

    if(count == 0) {
        count = num;
    } 
    else {
        incount++;

        let result = fibonacci(num);
        console.log(result[0] + " " + result[1]);

        if(count == incount) {
            rl.close();
        }
    }

});

function fibonacci(num) {
    if(num === 1) {
        let result = [0, 1];
        return result;
    }
    else if (num === 0) {
        let result = [1, 0];
        return result;
    }
    else if (dp[num] != undefined){
        return dp[num];
    }

    let temp1 = fibonacci(num - 1);
    let temp2 = fibonaacci(num - 2);
    let result = new Array();

    for (var i = 0; i< 2; i++) {
        result[i] = parseInt(temp1[i] + temp2[i]);
    }
    dp[num] = result;
    return dp[num];
}