toy2. Memorization

주어진 입력값에대한 결과를 저장함으로써 같은입력값에대한 함수가 한.번.만. 실행하도록 하는것

 

재귀를 통해 피보나치를 돌렸을때? => 같은 입력값에대해서 여러번 실행한다.

재귀를 트리형태로 생각해보면 트리의 가지가 엄청나게 많아진다.

 

//일반 재귀로 구현

function fibonacci(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.
 
 if(num === 0){
   return 0
 }
 if(num === 1){
   return 1
 }
return fibonacci(num-1) + fibonacci(num-2)
}

 

1.메모를 체크한다.

2. 계산결과를 메모에 저장 할 수있다. 

 

이렇게 구현하면 제귀트리에서 더이상 나타나지 않는다고한다.

 

fibonacci

문제

아래와 같이 정의된 피보나치 수열 중 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))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

 

---

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.

// dynamic with meoization: O(N)
// 이미 해결한 문제의 정답을 따로 기록해두고,
// 다시 해결하지 않는 기법

 const memo = [0,1] 

 const fibo = (n) => {
   if(memo[n] !== undefined){
     return memo[n]
   }else{
     memo[n] = fibo(n-2) + fibo(n-1)
     return memo[n]
   }
 }
 return fibo(n)
}

 

1. 메모 변수를 만든다. <= 계산결과를 메모에 저장하기위해 <= return memo[n]에서 볼 수있듯이 메모를 저장중이다.

2. 피보라는 재귀함수를 하나 따로 만든다.

3. 0,1 은 우선 담아줘야하며, 그 다음에 나오는것을 저장해야한다. undefined가 아니면 0이나 1이니까 바로 리턴.

4. 아닐시? 다시 memo[n] 에 재귀한것을 담아주고 memo[n]의 값을 리턴시켜야한다.

5. 리턴 Fibo(n)을 하는이유는 그안에서 리턴값이 memo[n]이기때문이다.