[프로그래머스][JS] 멀리 뛰기 ✅

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

프로그래머스

풀이 과정

function solution(n) {
    // n = 4
    const MOD = 1234567
    const dp = new Array(n + 1).fill(0)
    // console.log(dp) // [ 0, 0, 0, 0, 0 ]
    
    // 초기값을 설정하여 초기값을 바탕으로 n까지 순차적으로 값을 계산
    dp[1] = 1
    dp[2] = 2
    
    for (let i = 3; i <= n; i++){
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    }
    // console.log(dp) // [ 0, 1, 2, 3, 5 ]
    return dp[n];
}

동적 계획법(DP)은 문제를 작은 부분 문제로 나누고, 나눈 부분 문제들을 해결하여 큰 문제를 해결하는 알고리즘 설계 기법이다.

중복 계산을 피하기 위해 이전에 계산한 결과를 저장하고 재사용하는 방식으로 동작한다. 

위 코드에서 dp 배열을 생성할 때 n + 1인 이유는 dp [0]은 사용하지 않기 때문이다. 

dp [i]는 i칸을 뛰어서 도달할 수 있는 방법의 수를 나타내므로 배열의 인덱스와 칸 수를 일치시켜야 한다. 

이후에 dp[1]와 dp [2]의 초기값을 설정해야 한다. 피보나치수열을 구하는 방법을 생각해 보면 이전 값을 가지고 이후의 값을 계산한다.

이러한 재귀적 접근을 사용해야 문제를 풀 수 있다. 

반복문 또한 피보나치 수열을 구하는 방법과 유사한 방식을 적용하고 있다. 다만, DP의 핵심 원리 중 하나인 중복 계산을 피하기 위해 값을 저장하고 재사용하며, 이를 통해 효율적으로 문제를 해결한다.

---

리뷰

다이나믹 프로그래밍 문제는 처음 접근해 보는데 피보나치수열 문제 푸는 것과 유사했지만 스스로 풀어내기에는 어려웠다.