코플릿 - 동적 계획법(Dynamic Programming)

피보나치 수열 문제여서 평소처럼 이렇게 풀어서 제출을 했는데 

console.log(solution(+input[0]));

function solution(n) {
    if(n<2) {
        return n;
    }
    return solution(n-1) + solution(n-2)
}

시간초과가 떴다 그래서 문제 조건을 잘 살펴보니 피보나치 수열을 구하는 효율적인 알고리즘(O(N))이 존재한다고 해서 

구글링을 해봤는데 다이나믹 프로그래밍 이라는 걸 알게됨

이런 방법이 존재하는 이유가 일단 재귀함수를 이용해서 피보나치 수열을 구하면 중복연산이 많아져서 매우 비효율 적이라고 한다 

위에 코드처럼 하면 시간 복잡도가 O(2ᴺ) 이만큼 되버린다.

이게 무슨 의미냐면  예를 들어 50번째 피보나치 수열을 구하려고 하면 2의 50승 만큼의 연산을 해야한다는 의미이다.

(대략 이정도 1125899906842624)

이를 해결하기 위해 다이나믹 프로그래밍을 사용해서 한번 구한 작은 문제 결과 값을 또 계산하지 않고 저장해두고 사용을 하면 

시간 복잡도가 O(N) 이렇게 줄어든다 .

다이다믹 프로그래밍을 사용하기 위해서는 2가지 조건이 필요한데 출처 읽어보는게 나을듯 싶다.

1. 중복되는 부분 문제 (Overlapping Subproblem)
2. 최적 부분 구조 (Optimal Substructure)

출처 : https://hongjw1938.tistory.com/47    

그래서 DP를 이용해서 해결한 코드가 

const memo = [0]
function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
  if (n < 2) {
    return n;
  }
  if(memo[n] !== undefined) { // 이미 존재한다면 그대로 리턴
    return memo[n];
  }
  memo[n] = fibonacci(n - 1) + fibonacci(n - 2) // 없다면 새로 만들어주기 
  return memo[n];
}