그래.... 하나가 지나가니깐 또 하나가 나오네 ㅋㅋㅋㅋㅋㅋ

익숙해질법 하지만 새로운것을 볼때마다 머리가 아파온다 🤣 🤣

Dynamic Programming

Dynamic Programming(동적 계획법)은 모든 경우의 수를 따져본 후 이를 조합해 최적의 해법을 찾는 방식

Dynamic Programming의 원리는 주어진 문제를 여러 개의 하위문제로 나눠서 풀고, 하위문제들의 해결방법을 결합하여 최종문제를 해결하는 방식!

Dynamic Programming은 두가지의 조건이 충족되어야 사용가능하다.

1. 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제들은 중복된다. (Overlapping Sub-problems)

2. 작은 문제에서 구한 답은 이 문제를 포함하고 있는 큰 문제에서도 같다.
   즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용 할 수 있다. (Optimal Substructure)

Dynamic Programming 예시

피보나치 수열

function fib(n) {
	if(n <= 2) return 1;
	return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...

fib(7)을 구하기 위해서는 fib(6)을 ...

fib(6)을 구하기 위해서는 fib(5)을 ...

fib(5)을 구하기 위해서는 fib(4)을 ...

fib(4)을 구하기 위해서는 fib(3)을 ...

fib(3)을 구하기 위해서는 fib(2)을 ...

fib(2)을 구하기 위해서는 fib(1)을 ...

-> 가장 큰 문제를 해결하기 위해서 작은문제들을 계속 반복적으로 수행해야하는것을 확인 할 수 있다. (Overlapping Sub-problems)

-> 작은 문제에서 구한 정답을 큰 문제에서도 사용 할 수 있다. (Optimal Substructure)

(위의 코드는 콘솔창에 50이 되는 수만 입력해도 답이안나온다 ... 시간복잡도가 O(2^N) )

Recursion + Memoization

Memoization
동일한 작업을 반복하지 않기 위해 작은 문제를 해결책을 저장해서 사용하는 방법

function fibMemo(n, memo = []) {
    if(memo[n] !== undefined) return memo[n];
		// 이미 해결한 하위 문제인지 찾아본다
    if(n <= 2) return 1;
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
		// 없다면 재귀로 결과값을 도출하여 res 에 할당
    memo[n] = res;
		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
    return res;
}

위에서 아래로 내려가는 것처럼 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 이 방식을 Top-down 방식

시간복잡도는 O(N) - 이전의 피보나치 수열보다 속도가 엄청나게 빨라진 것을 볼 수 있음!!

Iteration + Tabulation

위 코드는 재귀를 사용한 코드!
아래의 코드는 반복문을 이용하여 Dynamic Programming을 구현
위의 재귀함수와 같이 하위문제의 결과를 저장해두고 필요할 때, 찾아서 사용하는 개념은 같다. 하지만 재귀함수를 이용한 방법은 큰 문제부터 시작해서 작은문제로 넘어가며 문제를 해결 했다면, 반복문은 작은 문제에서부터 시작하여 큰 문제를 해결해나가는 방식!

이를 Bottom-up 방식이라 부르기도 한다.

function fibTab(n) {
    if(n <= 2) return 1;
    let fibNum = [0, 1, 1];
		// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다 
    }
    return fibNum[n];
}

시간복잡도는 O(N)

함수실행 시간측정

Recursion + Memoization (Top-down)

Iteration + Tabulation (Bottom-up)

속도차이를 비교 해보았으닌 Top-down보다 Bottom-up이 더 빠르게 나왔다.
(오호?)
이유가 무엇일까 🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔
이전에 재귀보다 반복문의 속도가 더 빠르다고 배웠다. 그 이유인지 궁금하다 .. 정답은 무엇일까?
눈으로 보이는 결과는 어찌되었든 반복문을 사용한쪽이 더 빨랐다....

마무리

아직까지 Memoization을 이용하여 문제를 푸는방법이 너무 어색하고 어렵게 느껴진다.... 머리는 알겠지만 구현을 하는것은 역시 어려운 문제다.
유튜브도 참고하고 이것저것보면서 이해하고 있다. 하지만 역시 직접 문제를 풀면서 머리를 뜯는 고통을 겪는것이 가장 내가 배우는데 적합하지 않을까생각 된다 ㅋ
나만 어려운건 아니겠지? ㅠ... 힘내자 🔥🔥🔥🔥🔥🔥