재귀함수를 활용한 fibonacci수열 n번째 항의 수 찾기

문제

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.
0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

주의 사항

재귀함수를 이용해 구현해야 합니다.
반복문(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

풀이

function solution (n) {
	// 피보나치의 0과 1번째는 고정값이다.
	let newArr = [0, 1];
    
    let fibo = (n) => {
    	// 피보에 n번째 항의 값이 존재한다면 그대로 출력하면 됩니다.
    	if(newArr[n] !== undefined){
        	return newArr[n];
        }
        // 반대로 없는 값이라면 추가하여 넣어주면  출력하면 된다.
        // 피보나치 공식은 (n - 1) + (n - 2)다.
        newArr[n] = fibo(n - 1) + fibo(n - 2);
        return newArr[n];
    }
    return fibo(n);
}

오늘의 문제는 기존에 풀었던 문제라 쉽게 풀 수 있었다.

그래서 다른 이야기를 해보려고 한다.

프로그래밍을 하면서 우리는 왜 피보나치수와 관련된 공부와 코드를 짤 줄 알아야할까?

피보나치수열 소스코드를 활용하면 기하 급수적으로 늘어나는 문제를 해결할 수 있다.
다이나믹 프로그래밍을 사용해 효율적으로 문제를 해결할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
   피보나치 수열을 실무에서 사용하는 경우는 메모리제이션 기법을 사용하면 효과적으로 코드를 구현할 수 있다고 한다. 한 번 구한 결과를 메모리 공간에 메모해두고 다시 호출하는 경우 그대로 가져오는 기법이다. 메모리제이션을 다양한 곳에서 활용할 수 있지만 내가 아는 메모리제이션은 캐싱 뿐이다.
   여기서 더해 캐싱이란? 데이터 하위 집합을 저장하는 스토리지 계층이다. 캐싱을 사용하면 이전 검색, 계산한 데이터를 효율적으로 재사용할 수 있다.

다이나믹 프로그래밍, 캐싱, 메모리제이션 등 다양한 면접 질문이 나왔지만, 실제 코드에 대한 적용 및 사용경험이 없어 어려움을 겪었다.

다이나믹 프로그래밍이란?

• 큰 문제를 작은 단위로 나누어 푸는 기법