Portfolio

풀이

김영준


// n이 1일때 = 방법은 1개
// n이 2일때 = 방법은 2개
// n이 3일때 = 방법은 3개
// n이 4일때 = 방법은 5개
// n이 5일때 = 방법은 8개
// 피보나치 수열

function solution(n) {
   const arr = [];
    arr[0] = 1;
    arr[1] = 1;
    
    for(let i = 2; i <=n; i++){
        arr[i] = (arr[i-2] + arr[i-1] % 1234567);
    }
    return arr[n]  
}

이종현


// 피보나치 수열을 이용한 DP
function solution(n) {
    // 피보나치 수를 이용한 반복문을 돌리기 위해 3번째 index까지는 할당 단계에서 값을 넣어주고 시작
    const answer = [0, 1, 2];
    
    // 4번째 index부터는 현재 index의 값은 (index - 2) + (index - 1)  
    for (let i = 3; i <= n; i++) {
        answer[i] = (answer[i - 2] + answer[i - 1]) % 1234567;
    }
    
    return answer[n];
}

박노철


function solution(n) {
    //1칸 뛰기, 2칸뛰기 
    //1번으로 가는 방법=>0번에서 1칸뛰기(1가지), 2번으로 가는방법=> 1번에서 1칸, 0번에서 2칸(2가지)
    //3번으로 가는 방법=>2번에서 1칸(2번까지는 2가지), 1번에서2칸(1번까지는 1가지)(총 3가지 )
    //.....점화식은 dp[n]=dp[n-1]+dp[n-2]가 된다. 점화식을 위해 dp에 인덱스 2까지는 넣어주어야 한다. 
    // 숫자가 너무 커질수 있음으로 넣기전에 num으로 각각 나눈 나머지들을 합쳐서 넣어준다. 
    const dp=Array.from({length:n+1}, ()=>0);
    dp[1]=1;
    dp[2]=2;
    const num=1234567;
    for(let i=3; i<=n; i++){
        dp[i]=(dp[i-1]%num)+(dp[i-2]%num);
    }
    return dp[n]%num;
}

이민희


/* 첫 번째 풀이 - 테스트 케이스 7 ~ 16 실패
n이 2000인 경우 1000!을 돌리게 되는데, 
1000!은 Infinity.... 가 돼서 %1234567을 하면 NaN이 나와서 그런 것 같아요.
 */

// 2의 개수를 기준으로 경우를 나누고,
// 각 경우에서 나올 수 있는 순서들의 수만큼 곱해줍니다.
function solution(n) {
    let cnt = 0;
    
    // 한 사이클마다 2의 개수를 하나씩 줄이고, 1은 두 개씩 늘려갑니다.
    for (let i = Math.floor(n / 2); i >= 0; i--) {
        const cnt2 = i;
        const cnt1 = n - (cnt2 * 2); // 22211 5!/3!*2!
        cnt += factorial(cnt2 + cnt1) / (factorial(cnt2) * factorial(cnt1)); // 해당 조합으로 가능한 순서만큼 더해줍니다.
    }
    return cnt % 1234567;
}

function factorial(n) {
    if (n <= 1) return 1;
    else return n * factorial(n - 1);
}


// 칸이 n개인 경우, 칸이 n-2개였을 때의 방법에서 2칸만 더 가면 되고, 칸이 n-1개였을 때의 방법에서 1칸만 더 가면 됩니다.
// 즉, 두 방법의 개수를 합한 만큼이 n칸의 끝에 도달하는 방법입니다.
// -> dp로 풀 수 있습니다.
function solution(n) {
    const dp = new Array(n).fill(1234567);
    dp[1] = 1;
    dp[2] = 2; // 1 1, 2
    
    for (let i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
    }
    return dp[n];
}

박건우


function solution(n) {
    const dp = Array.from({length : n + 1}, () => 0);
    dp[1] = 1;
    dp[0] = 1;
    
    for(let i = 2; i<=n; i+=1){
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
    }
    
    return dp[n];
}

// DP로 풀었습니다!
// n번째 칸에 도착하는 방법은 n-1번째 칸에서 한칸 점프하는 방법 + n-2번째 칸에서 두칸 점프하는 방법
// 따라서 점화식은 dp[n] = dp[n-1] + dp[n-2]

박주연


//1️⃣ 입력: 2000이하 => 거의 모든 알고리즘 유형으로 풀 수있겠구나 하고 접근
//2️⃣ 직접 n=7까지 수기로 경우의 수를 다 계산해서 dp[i] = dp[i-1] + dp[i-2] 점화식을 알아냈습니다.
//3️⃣ 처음 푼 풀이 => 실패. 정수 오버플로우 발생
//자바스크립트에서 산술 연산의 결과가 표현할 수 있는 가장 큰 수 보다 더 크다면 
//오버플로우(Overflow)가 발생하며 무한대를 의미하는 Infinity 값을 출력합니다.
//자바스크립트에서 숫자는 모두 '64 비트 IEEE 754 형식'으로 다뤄진다.
//안전한 가장 큰 정수는 9007199254740991, 가장 작은 정수는 -9007199254740991이다.

function solution(n) {
    const dp = Array.from({length: n},() =>0);
    dp[0] = 1;
    dp[1] = 2;
    
    for(let i = 2; i < n ; i++){
        dp[i] = dp[i-1] + dp[i-2];  
    }
    console.log(dp)
    return dp[n-1] % 1234567
}

//4️⃣ 성공한 풀이
function solution(n) {
    const dp = Array.from({length: n},() =>0);
    dp[0] = 1;
    dp[1] = 2;
    
    for(let i = 2; i < n ; i++){
        dp[i] = (dp[i-1] + dp[i-2])% 1234567;  
    }
    return dp[n-1]
}

멀리뛰기

풀이