๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

[Javascript] ํŒŒ๋ณด๋‚˜์น˜ ์ˆ˜ (12945)

๋ฌธ์ œ๋งํฌ

 

์ ‘๊ทผ๋ฐฉ๋ฒ•

๋‘๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค.

1. ์žฌ๊ท€์ ์œผ๋กœ ํƒ์ƒ‰
์ข…๋ฃŒ ์กฐ๊ฑด : num === 0 ์ผ๋•Œ 0, num === 1 ์ผ๋•Œ 1์„ returnํ•˜๊ณ 
์žฌ๊ท€ ์กฐ๊ฑด์œผ๋กœ return fibo(num-1) + fibo(num-2) ๋ฅผ ๊ณ„์†ํ•ด์„œ ํ˜ธ์ถœํ•˜๋ฉด ๋œ๋‹ค.
const fibo = (num) => {
    if(num === 1) return 1;
    else if(num === 0) return 0;
    let result = (fibo(num-1) + fibo(num-2)) % 1234567
    return result
}โ€‹

์ž‘์€ ์ˆ˜์—์„œ๋Š” ์ •์ƒ ์ž‘๋™ ํ•˜์ง€๋งŒ (%1234567)์„ ์–ด๋””์— ๋„ฃ์–ด์•ผ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์—์„œ ํ†ต๊ณผํ•˜๋Š”์ง€ ๋ชจ๋ฅด๊ฒ ๋‹ค..

2. dynamic Programing ๋ฐฉ์‹์œผ๋กœ ํƒ์ƒ‰
n ํฌ๊ธฐ์˜ dp ๋ฐฐ์—ด์„ ๋งŒ๋“ค๊ณ  ์ดˆ๊ธฐ๊ฐ’ dp[0], dp[1]์„ ํ• ๋‹น ํ•ด์ค€ ๋’ค,
 
dp[n] = dp[n-1] + dp[n-2]๋ผ๋Š” ํ”ผ๋ณด๋‚˜์น˜ ๊ณต์‹์„ ๊ทธ๋Œ€๋กœ ์‚ฌ์šฉํ•˜์—ฌ ๊ฒฐ๊ณผ๊ฐ’์„ ๊ตฌํ•œ๋‹ค.
dp[0] = 0;
dp[1] = 1;
for(let num = 2; num <= n; num++){
    dp[num] = (dp[num-1] + dp[num-2]) % 1234567
}โ€‹


 

 

// dp ๋ฐฉ๋ฒ•

function solution(n) {
    let dp = Array.from({length : n}, () => 0);
    
    dp[0] = 0;
    dp[1] = 1;
    for(let num = 2; num <= n; num++){
        dp[num] = (dp[num-1] + dp[num-2]) % 1234567
    }
    
    return dp[n];
}
// ์žฌ๊ท€ ๋ฐฉ๋ฒ•

function solution(n) {
    
    const fibo = (num) => {
        if(num === 1) return 1;
        else if(num === 0) return 0;
        let result = (fibo(num-1) + fibo(num-2)) % 1234567
        return result
    }
    
    return fibo(n);
}