[TDL] 06/15 Today's-Done-List

- udemy 알고리즘 강의 (재귀 문제 2개)

하루에 1-2문제 풀기 챌린지 중!

오늘 피보나치 재귀를 풀었는데, 유데미 강의에서는 이번 퀴즈는 그냥 솔루션만 알려주었기에 완벽히 이해하고 싶어서 구글링을 하는데, 다들 내가 받은 솔루션 코드가 시간 복잡도가 최악이라는 말을 하고 있다.... 왜 이런 걸 알려준 거야?ㅠ

피보나치 수열이란? 각 숫자가 직전의 두 숫자의 합인 수열이다.
fib(10)를 구하기 위해 0부터 10번째까지의 수들을 나열해본다면,
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]이며 fib(10)는 fib(10)는 21+34로  55이다.
fib(4)를 구하기 위해 0부터 4번째까지의 수들을 나열해본다면, [0, 1, 1, 2, 3] 1+2로 3이다.

문제는 피보나치의 n번째 수를 출력하는 것이었는데, 내가 받은 솔루션 코드는 이렇다.

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

나는 현재 재귀를 공부하고 있기 때문에, 반복문 말고 재귀 함수를 사용한 솔루션인데 fib 함수는 매번 자기 자신을 두 번 불러내야 하므로, n이 커질 때마다 처리능력이 두배가 필요함. 그러므로 시간 복잡도가 O(2n)으로, 최악이라 한다.

---

그렇다면 어떻게 해야 재귀 함수를 사용한 코드를 개선할 수 있을까?

재귀 함수는 말 그대로 자기 자신을 반복해서 불러내는 함수로, 같은 인자로 같은 함수를 여러 번 반복하게 된다.
그렇기 때문에 반복하여 실행하지 않도록 해준다면 어떨까?

함수와 실행될 인자와 그 결과를 저장하고, 만약 함수가 같은 인자로 다시 실행된다면 미리 저장되어 있던 결과를 반환한다. 이렇게 된다면 함수를 매번 다시 실행할 필요가 없게 되므로, 시간 복잡도가 훨씬 개선된다.

var arr =[0, 1]; 

function fib(n) {
    if(arr[n] == undefined) {
        arr[n] = fib(n - 1) + fib(n - 2);
    }
    return arr[n];
}

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

function memoize(fn) { 
    const save = {}; 
    return function(...args) { 
    	if (save[args]) { 
            return save[args]; 
        } 
        const result = fn.apply(this, args); 
        save[args] = result; 
        return result; 
    } 
} 

const fib = memoize(fibo);

https://www.zerocho.com/category/JavaScript/post/579248728241b6f43951af19

https://www.zerocho.com/category/JavaScript/post/579248728241b6f43951af19

https://alithedeveloper.tistory.com/m/24?category=996348

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

https://bibi6666667.tistory.com/99

[인프런] Javascript - 재귀의 기초2 (점화식, 피보나치수열, 다이나믹 프로그래밍 memoization)

---

- 프로그래머스 js스터디

 

---