알고리즘 문제풀이 toy - fibonacci

 

 

문제 설명: 일반적인 피보나치 수열의 문제지만 알고리즘(O(N))의 속도가 나오도록 구현해야한다.

그래서 여기서는 중복 계산되는 것을 방지하게끔 코딩해야한다.

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
  
  
  

입력

인자 1 : n

• number 타입의 n (n은 0 이상의 정수)
  
  
  

출력

• number 타입을 리턴해야합니다.
  
  
  

주의사항

• 재귀함수를 이용해 구현해야 합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.
  
  
  

입출력 예시

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(N))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

// 일반적인 피보나치 수열 알고리즘이지만 이 것은 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, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

 

다른 말로 "기억하며 풀기" 라고 부르기도 한다.  그러면 알고리즘을 계산할 때  다이나믹프로그래밍 메모이제이션을 썼을 때와 안 썼을 때 얼마나 차이나길래 이 방법으로 코딩을 하는 것일까? 대략적인 연산 횟수의 차이는 다음과 같다.

 

 

동적 계획법의 개념과 구현에 대해 정확하게 짚고 넘어가기 위해 동적 계획법을 적용시킬 수 있는 예에 대해 알아보자.

• f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )
• f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1

위와 같이 정의된 함수에서 주어진 임의의 a,b에 대해 f(a,b)의 값을 효율적으로 구하고자 할 때 동적 계획법을 적용시킬 수 있다.

f(2,2) = f(1,2) + f(2,1)

f(1,2) = f(0,2) + f(1,1)

f(2,1) = f(2,0) + f(1,1)

f(1,1) = f(0,1) + f(1,0) 

......

예를 들어 f(2,2)을 계산한다고 해보자. f(2,2)를 계산할 때는 1밖에 연산차이가 나지 않지만
(4,4)일때는 53, (6,8)일때는 2954, (10,10)일때는 무려 184655 차이가 난다. 
배수로 따지면 (10,10)일때는 1847배(184755/100) 정도 차이가 난다. 

 

이정도 차이면 동적계획법의 효율이 느껴진다. 

 

 

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 나무위키