문제 : fibonacci

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

문제의 접근

피나보치는 재귀함수의 코플릿을 풀 때 한번 접해 본적이 있었다. 그래서 그 때의 기억을 가지고 코드를 작성해 보았다.

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
  if(n <= 1){
    return n
  }
  return fibonacci(n-1) + fibonacci(n-2)
}

하지만 위 코드를 실행해보니 실행시간을 초과한다고 나왔다. 아마도 Advanced문제까지 한번에 해결해야 할 것 같았다. 그렇다면 어떤 방법을 써야할까?
당연히 생각난 부분은 동적 할당을 사용하는 방법이다. 하지만 상향식을 사용하기 위해서는 for문, while문이 필수이나 문제에서 사용을 금하고 있다. 그렇다면 당연히 남은 건 하향식 동적 할당으로 문제를 해결해야 겠다고 생각했다. 그 코드는 다음과 같다.

function fibonacci(n, m=[]) {
  // TODO: 여기에 코드를 작성합니다.
  let result = 0;
  if(m[n] !== undefined){
    return m[n] 
  }
  if(n<=1){
    return n
  }
  result = fibonacci(n-1,m) + fibonacci(n-2,m)
  m[n] = result;
  
  return result;
}

위 방식을 이용한다면 이미 계산한 값들은 m에 저장되었다가 필요할 때 호출만 하면 되기 때문에 다시 연산을 할 필요가 없어 더 효육적인 사용이 가능하다.

Advanced

위 코드를 사용하면 한번에 통과 가능하다.

문제를 통해 생각해 볼 것

위 문제는 사실 내가 직접 생각해낸 것 보다는 기존에 동적 할당의 예시로 한번 봤던 코드이기 때문에 쉽게 코드를 작성 할 수 있었다. 하지만 이와 비슷한 문제가 나오지 말라는 법은 없다. 충분히 활용 방법을 연습해서 이와 비슷한 문제를 대비 해야 겠다.