문제 설명: 일반적인 피보나치 수열의 문제지만 알고리즘(O(N))의 속도가 나오도록 구현해야한다.
그래서 여기서는 중복 계산되는 것을 방지하게끔 코딩해야한다.
입력
인자 1 : n
출력
주의사항
입출력 예시
let output = fibonacci(0);
console.log(output); // --> 0
output = fibonacci(1);
console.log(output); // --> 1
output = fibonacci(5);
console.log(output); // --> 5
output = fibonacci(9);
console.log(output); // --> 34
Advanced
// 일반적인 피보나치 수열 알고리즘이지만 이 것은 O(2^N)의 효율이라서 문제와 맞지 않다.
// naive solution: O(2^N)
// let fibonacci = function (n) {
// if (n <= 1) return n;
// return fibonacci(n - 1) + fibonacci(n - 2);
// };
// 다이나믹 프로그래밍 메모이제이션
// dynamic with meoization: O(N)
// 이미 해결한 문제의 정답을 따로 기록해두고,
// 다시 해결하지 않는 기법
// fibo(10)
// = fibo(9) + fibo(8)
// = fibo(8) + fibo(7) + fibo(7) + fibo(6)
// 여기까지만 보아도 동일한 문제가 중복으로 계산되는 것을 알 수 있다.
let fibonacci = function (n) {
const result_arr = [0, 1];
const fibo_arr = (n) => {
// 이미 해결한 적이 있으면, 메모해둔 정답을 리턴한다.
if (result_arr[n] !== undefined) return result_arr[n];
// 새롭게 풀어야하는 경우, 문제를 풀고 메모해둔다.
result_arr[n] = fibo_arr(n - 1) + fibo_arr(n - 2);
return result_arr[n];
};
return fibo_arr(n);
};
다이나믹 프로그래밍 메모이제이션이란?
DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.
다른 말로 "기억하며 풀기" 라고 부르기도 한다. 그러면 알고리즘을 계산할 때 다이나믹프로그래밍 메모이제이션을 썼을 때와 안 썼을 때 얼마나 차이나길래 이 방법으로 코딩을 하는 것일까? 대략적인 연산 횟수의 차이는 다음과 같다.
이정도 차이면 동적계획법의 효율이 느껴진다.
https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95
알고리즘 문제풀이 toy - bubbleSort (0) | 2023.01.04 |
---|---|
알고리즘 문제풀이 - toy isSubsetOf 문제 (0) | 2023.01.03 |
알고리즘 문제풀이 toy - orderOfPresentation (0) | 2022.12.30 |
알고리즘 문제풀이 - compressString (2) | 2022.12.29 |
알고리즘 문제풀이 - decryptCaesarCipher (0) | 2022.12.29 |