Memoization, fibonacci

Memoization?

• 메모
• 반복되는 결과 ⇒ 메모리에 저장
• 나중에 필요할때 꺼내 쓴다.

javaScript에서 클로저를 통해 계속 유지되는 저장공간 만들 수 있다.

이것을 이용해 Memoization 패턴구현

재귀로 피보나치 수열을 구하는 문제에 접근하는 과정에서 재귀를 이용하면 엄청난 반복이 실행된다는 것을 알게되었다. 이를 더 효율적으로 구할수 있는 방법을 알아보자.

이미 계산한 내용을 메모리에 저장하고 필요한 경우 불러온다.

Memoization을 이용해 피보나치를 구현 하려면?

내가 생각한 재귀적 방식을 풀어서 적어봤다.
확실히 적고 나니까 드디어 느낌을 알게되었다.

손코딩 작성 후 나는 이제 재귀와 눈맞춤 정도는 할 수 있다.

let fibonacci = function (n) {
  const memo = [0, 1];
  const fibo = (n) => {
    // 이미 해결한 적이 있으면, 꺼내 쓰자
    if (memo[n] !== undefined) return memo[n];
    // 메모에 없으면, 재귀 호출을 통해 메모에 저장하자
    memo[n] = fibo(n - 1) + fibo(n - 2);
    return memo[n];
  };
  return fibo(n);
};


fibonacci(5)
let fibonacci = function (5) {
  const memo = [0, 1];
  const fibo = (5) => {
    if (memo[5] !== undefined) return memo[n]; //-> undefined pass
     // 메모에 없으면, 재귀 호출을 통해 메모에 저장하자
    memo[5] = fibo(4) +fibo(3); 
    return memo[n]; 
  };
  return fibo(n);
};

let fibonacci = function (5) {
  const memo = [0, 1];
  const fibo = (4) => {
    if (memo[4] !== undefined) return memo[n]; //-> undefined pass
    // 메모에 없으면, 재귀 호출을 통해 메모에 저장하자
    memo[4] = fibo(3) + fibo(2); 
    return memo[n]; 
  };
  return fibo(n);
};

let fibonacci = function (5) {
  const memo = [0, 1];
  const fibo = (3) => {
    if (memo[3] !== undefined) return memo[n]; //-> undefined pass
    // 메모에 없으면, 재귀 호출을 통해 메모에 저장하자
    memo[3] = fibo(2) + fibo(0);  -> memo[3] = fibo(2) + 0
    return memo[n]; 
  };
  return fibo(n);
};

let fibonacci = function (5) {
  const memo = [0, 1];
  const fibo = (2) => {
    if (memo[2] !== undefined) return memo[n]; //-> undefined pass
    // 메모에 없으면, 재귀 호출을 통해 메모에 저장하자
    memo[2] = fibo(1) + 0; // memo[2] = 1 + 0  // 여기 저장 meno에 추가
    return memo[n];  
		//fibo(2)일때 값은? 리턴값 1이다. 
  };
  return fibo(n);
};

let fibonacci = function (5) {
  const memo = [0, 1, 1];
  const fibo = (3) => { //2, 1
		// 이미 해결한 적이 있으면, 꺼내 쓰자
    if (memo[2] !== undefined) return memo[2]; // -> 1 
		if (memo[1] !== undefined) return memo[1]; // -> 1 
    메모에 없으면, 재귀 호출을 통해 메모에 저장하자
    memo[3] = fibo(2) + fibo(1); // memo[3] = 1 + 1 //여기 저장 meno에 추가
    return memo[n]; // fibo(3)은 memo[3]인 2다.
  };
  return fibo(n);
};

let fibonacci = function (5) {
  const memo = [0, 1, 1, 2];
  const fibo = (4) => { //3, 2
    // 이미 해결한 적이 있으면, 꺼내 쓰자
		if (memo[3] !== undefined) return memo[3]; // -> 2
    if (memo[2] !== undefined) return memo[2]; // -> 1
    // 새롭게 풀어야하는 경우, 문제를 풀고 메모해둔다.
    memo[4] = fibo(3) + fibo(2);  memo[4] = 2 + 1  //여기 저장 meno에 추가 
    return memo[n]; // fibo(4)은 memo[4]인 3다.
  };
  return fibo(n);
};

let fibonacci = function (5) {
  const memo = [0, 1, 1, 2, 3, 5];
  const fibo = (5) => {
    // 이미 해결한 적이 있으면, 메모해둔 정답을 리턴한다.
		if (memo[4] !== undefined) return memo[4]; // ->3
    if (memo[3] !== undefined) return memo[3]; // ->2
    // 새롭게 풀어야하는 경우, 문제를 풀고 메모해둔다.
    memo[5] = fibo(4) + fibo(3);  memo[5] = 3 + 2 =5  //여기 저장 meno에 추가
    return memo[5]; // fibo(5)은 memo[5]인 5다.
  };
  return fibo(n); //-> 5
};