[알고리즘 with JS] 피보나치 수열

문제

피보나치 수열의 n번째 숫자를 출력하라. 피보나치 수열은 각 숫자가 직전의 두 숫자의 합인 수열이다. 

그 예로, 다음 배열은 피보나치 수열의 첫 10개 수를 나타낸다.

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

 

답안 예시: 

fib(4) === 3;

fib(7) === 13;

 

Solution 1 - 반복문 사용: O(n)

function fib(n) { 
	const result = [0, 1]; 
    for (let i = 2; i <= n; i++) { 
    	const a = result[i - 1]; 
        const b = result[i - 2]; 
        result.push(a + b); 
    } 
    return result[n]; 
 }

 

Solution 2 - 재귀함수 사용: O(2ⁿ)

• 재귀함수: 자기 자신을 불러내는 함수. 아래 코드블럭의 다섯번째 줄에서 함수가 스스로를 다시 활용하는 것을 볼 수 있다.

function fib(n) { 
    if (n < 2) { 
    	return n; 
    } 
    return fib(n - 1) + fib(n - 2); 
}

• fib 함수는 매 번 자기 자신을 두 번 불러내는 것을 볼 수 있다. 따라서 n이 커질 때 마다 처리능력은 두배가 필요하다. 
• 시간 복잡도가 최악이다. 컴퓨터에 따라 조금씩 다르겠지만, n=50 정도면 이미 사용하기가 어려울 정도로 느려진다. 

 

반응형

 

재귀함수 사용한 해법 개선하기: Memoization

• 재귀함수는 자기 자신을 반복해서 불러낸다. 위의 fib 함수의 경우, 같은 인자로 같은 함수를 여러 번 반복하여 불러내고, 그럴 때마다 매번 같은 결과를 반환한다. 그렇기 때문에 똑같은 인자로 함수를 반복하여 실행하지 않도록 해주면 시간복잡도가 훨씬 개선된다.
• 함수가 실행될 때 인자(arguments)와 그 결과를 저장한다. 만약 함수가 같은 인자로 다시 실행되면, 미리 저장되어있던 결과를 반환한다. 그렇기 때문에 함수를 매번 다시 실행할 필요가 없다.
• 아래의 memoize 함수는 어떤 함수에도 다 쓰일 수 있는 범용 함수이다. 인자로 개선할 어떤 함수든 처리할 수 있다.

function slowFib(n) {
	if (n < 2) {
    	return n; 
    } 
    
    return fib(n-2) + fib(n-1) 
} 

//Generic Momoization Function 
function memoize(fn) { 
    const cache = {}; 
    return function(...args) { 
    	if (cache[args]) { 
            return cache[args]; 
        } 
        const result = fn.apply(this, args); 
        cache[args] = result; 
        return result; 
    } 
} 

const fib = memoize(slowFib);

 

 

 

 

이 포스팅은 Udemy의 강의 The Coding Interview Bootcamp: Algorithms + Data Structures의 일부를 요약한 내용입니다.