D+2 멀리뛰기 js

프로그래머스 코테 풀기 멀리뛰기

const fibonacci = (n) => {
    let dp = [1,1]
    for (i=2; i<=n; i++){
        dp[i] = (dp[i-1]+ dp[i-2]) % 1234567;
    }
    return dp[n]
}
function solution(n) {
    return fibonacci(n)
}

DP (다이나믹 프로그래밍) =기억하기 알고리즘

(수행시간 단축기법)

1.목적 : 메모리를 사용해서 중복연산을 줄이고 중복 연산을 줄여서 수행속도를 개선한다.
메모리를 사용한다 -> 배열 혹은 자료구조를 만든다
중복 연산을 줄인다 -> 연산한 결과를 배열에 담는다

2. 다이나믹 프로그래밍 문제를 알아보고 구분하는 방법
특정 문제에 국한되지 않고 다양한 문제를 최적화할 때 고려될 수 있는 알고리즘

3.판단 기준
1) DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많은 존재는 X
ㄴ완전탐색으로 풀 수있는 마지노선은 약 500만개
2) 패턴찾기 - 처음부터 수학적으로 정리할 필요없고, 처음 . 몇개는 손으로 직접 세보고 패턴이 보이면 그때 계산해서 수학적인 식 도출
3) 경우의 수들에 중복적인 연산이 많은 경우

4.문제해결접근방법
DP는 최대한 많은 문제를 풀어보고 풀이들을 참고하면서 DP식의 사고방식을 습득, 오래 붙잡고 있기 보다는 30분 고민해보고 답이 안나오면 풀이 참고해서 구현해보기.
연산을 또 하지 않으려면 어떤 정보를 남겨야 하지? 어떤 식으로 정보를 누적해야 최적화될지?를 고민하고 저장하기