[백준 2747번 node.js] 피보나치 수

https://www.acmicpc.net/problem/2747

 

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하기

---

동적 프로그래밍 (Dynamic Programming - DP)

큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있을 때 프로그램의 속도를 비약적으로 향상 시킴

쉽게 말해서, 메모리를 사용해서 중 복 연산을 줄이고 중복 연산을 줄여서 수행 속도를 개선한다

 

 

가장 처음에 푼것은 DP의 가장 중요한 포인트는 죄다 던져두고 지멋대로 풀었다.

 

let num = 10;//테스트 인풋

function fibonacci(n) {
  if(n < 2) return n;

  let a = 0, b = 1, temp;

  for(let i = 2; i <= n; i++){
    temp = a + b;
    a = b;
    b = temp;

    console.log('a: ' + a + ' b: ' + b, 'temp: ' + temp, 'n:', n);
    
  }

  return b;
}


console.log(fibonacci(num));

 

하지만 이 문제에서 가장 중요한 것은

 

반복되는연산을 다시 수행하지 않는것!!!!!!!!

 

우선 재귀함수를 적용했을 때 ( 직관적이지만 여전히 같은 연산을 반복수행함 -> 비효율적)

let num = 10; // 테스트 인풋

function fibonacci(n) {
  if (n < 2) return n;

  console.log('n:', n);

  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(num));

---

메모이제이션을 적용했을 때

let num = 10; // 테스트 인풋

function fibonacci(n, memo = {}) {
  if (n < 2) return n;

  if (memo[n] !== undefined) {
    return memo[n];
  }

  console.log('n:', n);

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

console.log(fibonacci(num));

 

 

메모이제이션(Memoization)은 컴퓨터 프로그램에서 동일한 계산을 반복해야 할 때, 이전에 계산된 결과를 저장하여 재사용하는

기술!! 

 

1. memo 객체: memo는 이미 계산된 피보나치 수열 값을 저장하는 데 사용

2. 재귀 호출: 함수는 fibonacci(n-1, memo)와 fibonacci(n-2, memo)를 재귀적으로 호출

3. 저장된 값 사용: 이미 계산된 값이 memo에 저장되어 있다면, 그 값을 반환하여 다시 계산하지 않음

4. 값 저장: 계산된 값은 memo[n]에 저장되어 해당값을 리턴함