๐Ÿ”’Algorithm

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ํ’€์ด(js) > ๋ฉ€๋ฆฌ๋›ฐ๊ธฐ(lv2)

devWarrior 2023. 6. 27. 21:00

๋ฌธ์ œ ๐Ÿ”ฝ

https://school.programmers.co.kr/learn/courses/30/lessons/12914

 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr

๋‹ค๋ฅธ์‚ฌ๋žŒ ํ’€์ด ๐Ÿ”ฝ


function solution(n) {
    var answer = 0;
    var dp=[];
    dp[1]=1;
    dp[2]=2;
    for(var i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2] %1234567;
    }
    answer=dp[n];
    return answer%1234567;
}

๋‚ดํ’€์ด๐Ÿ”ฝ

1. ์‹คํŒจ โŒ => ( ์‹œ๊ฐ„์ดˆ๊ณผ : dfs๋กœ ์žฌ๊ท€ ์“ฐ๋ฉด ๋„ˆ๋ฌด ์˜ค๋ž˜๊ฑธ๋ฆผ ) 

// nC0 ~ nCn ๊นŒ์ง€ ํ•˜๋ฉด ๋ ๋“ฏ ํ•˜๋‹ค 
function solution(n) {
    var answer = 0;    
    const dfs =(count) =>{
        if(count>n){
            return 0;
        }else if(count===n){
            ++answer
            return 0;
        }
        dfs(count+1);
        dfs(count+2);
    }
    
    dfs(0)
    return answer%1234567;
}

2. ์„ฑ๊ณต โญ• => ( ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์ด์šฉ ) 

function solution(n) {

    if(n===1){
        return 1
    }
    if(n===2){
        return 2
    }

    let array=[0,1,2]
    for(let i=3; i<=n; i++){
        array[i]=(array[i-2]+array[i-1])%1234567
    }

    return array[n];
}

 

 

๋А๋‚€์ ๐Ÿ”ฝ

array[i] = (array[i-2]+array[i-1]) %1234567 ์˜ ๊ฐ’๊ณผ

array[i] = array[i-2]%1234567+array[i-1]%1234567์˜ ๊ฐ’๊ณผ ๊ฐ™๋‹ค