[백준/2.분할정복,이분탐색] 2747번. 피보나치 수(JavaScript)

방법1 시간초과 발생

https://www.acmicpc.net/problem/2747

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

let input;
rl.on("line", function (line) { //한 줄 입력
    input = line;
    input = parseInt(line);
    //rl.close()가 없어서 계속입력 
    //로컬에서 입력을 중지할려면 입력을 한 후 'ctrl + D'을 통해 입력 종료 
}).on("close", function () {
    // 이런식으로 적절하게 입력값을 처리해줘야한다. 
    
    console.log(fibo(input));

    //프로세스 종료 
    process.exit();
});


// const n = 10;

function fibo(n) {
    if (n == 0) {
        return 0
    }
    if (n == 1) {
        return 1
    }
    return fibo(n - 1) + fibo(n - 2)
}

재귀는 40~50 정도의 깊이면 시간이 많이 걸린다고 했는데,

문제는 45보다 작거나 같은 자연수라고 해서, 재귀함수를 사용하면 시간초과가 났다.

이미 계산한 것을 또 다시 계산해야하기 때문이다.

 

방법2 반복문 사용 

// 백준 제출을 위한 코드
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let input;
rl.on("line", function (line) { //한 줄 입력
    input = line;
    input = parseInt(line);
}).on("close", function () {
    console.log(fibo(input));

    process.exit(); //프로세스 종료 
});

// const n = 10;

function fibo(n) {
    let result = 0;
    let num1 = 1;
    let num2 = 1;
    if (n <= 2) {
        return 1;
    }
    for (let i = 3; i <= n; i++) {
        result = num1 + num2;
        num1 = num2;
        num2 = result;
    }
    return result;
}
// console.log(fibo(n));

이전에 피보나치 수열에서 계산한 값을 기억하고 있으면 된다.

재귀함수와 달리 불필요한 연산을 하지 않을 수 있어서 시간초과가 발생하지 않는다.