Dynamic Programming _ Memoization 설명 및 적용 #1

Why ? What is Dynamic Programming? 🧐

 

피보나치수열 예시 _

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

 

위 식에서 fib(7) 값을 트리로 나타내면 아래처럼 그릴 수 있는데요 

여기서 이 그래프의 구성을 보면 fib(2) + fib(1) = 1+1 = fib(3) 이런 식으로 자식노드의 피보나치 수열의 합이 곧 부모노드의 피보나치 수열값과 같음을 알 수 있습니다

 

 

이런식의 재귀 접근은 위 그래프는 O(2^n) time complexity 와 O(n) space complexity 를 가지기 때문에 비효율적입니다

 

여기서 어떤 비효율이 발생하고 있는지를 살펴보면 각 가지마다 반복되는 구간이 존재하고 각 자식노드가 root 보다 작은

피보나치 수열로 이루어진 걸 알 수 있습니다! 이렇게 하나의 큰 문제를 여러개의 작은 문제로 쪼개는게 Dynamic Programming입니다

 

 

비효율을 없애기 위해 기존의 계산값을 memo라는 dict 형태에 담아놓는 코드를 추가했습니다.

const fib = (n, memo ={}) => {
	if (n in memo) return memo[n];
	if (n<=2) return 1;
    memo[n] = fib(n-1,memo) + fib(n-2,memo);
    return memo[n]
    };

 

이 코드에는 코드가 돌아가는 과정에서 memo에 fib(3),fib(4),fib(5) 등 이미 계산된 피보나치 수열 값이 있기 때문에

새로운 중복되는 노드들을 없애고 계산에 필요한 노드만 고려해보면 아래와 같이 곧 2개의 노드가 n 번 반복되는

O(2n) = O(n)의 시간복잡도를 가지는 효율적인 계산으로 변모하게 됩니다

 

 

 

Grid Traveler 예시 _

 

m*n의 grid 에서 좌측상단에서 우측하단으로 움직이는 경우를 생각해보겠습니다

(단, 우측과 하단으로만 움직일 수 있습니다.)

 

가장 작은 m,n으로 생각해보면

gridTraveler(3,3) 을 아래로 한칸 가면 grid(2,3) 의 subproblem,

한칸 내려가면 grid(1,3) , 우측으로 2칸을  가면 gridTraveler(1,1) 하위 문제로 전개됨을 알 수 있습니다

 

✔

3*3 grid  ↓

✔

2*3 grid   ↓

✔

1*3 grid   ↓

✔

1*1 grid

 

이 과정을 tree로 나타내보면 결국 2*3의 경로의 수는 곧 아래로 가는 경우의 수 + 오른쪽으로 가는 경우의 수의 합으로 볼 수 있습니다. 이렇게 tree구조로 그림을 그릴 수 있는 것 자체가 새로운 접근인 것 같네요

 

 

input이 m과 n을 고려했을 때, 이 tree의 높이는 (m+n) 이고 각 노드가 2개의 자식노드를 가진다고 생각하면

time complexity가 O(2^(m+n))임을 알 수 있습니다. 또한, 이 tree의 높이는 재귀가 갈 수 있는 최대 깊이를 의미하므로

space complexity는 O(m+n)입니다.

 

이렇게 알게된 패턴을 바탕으로 코드를 작성하면 아래와 같습니다.

 

const gridTraveler = (m,n) => {
    if (m === 1&& n === 1) return 1;
    if (m === 0 || n === 0) return 0;
    return gridTraveler(m-1,n) + gridTraveler(m,n-1);
};

 

하지만 이 코드는 time complexity로 비효율적이라는 단점이 있는데요

 어떤 부분이 겹치는지, 효율성이 개선될 수 있는지 보면 사실상 gridTraveler(a,b) = gridTraveler(b,a) 로 계산을 중복으로

할 필요가 없음을 알게됩니다

 

 

이 부분에 memoization 을 적용해보겠습니다

const gridTraveler = (m,n,memo={}) => {
    const key = m +',' + n;
    if (key in memo) return memo[key]
    if (m === 1&& n === 1) return 1;
    if (m === 0 || n === 0) return 0;
    memo[key] = gridTraveler(m-1,n,memo) + gridTraveler(m,n-1,memo);
    return memo[key];
};

 이 memoized 버전의 time complexity는 곧 m=4, n =3 일때 {0,1,2,3,4}와 {0,1,2,3}이 가질 수 있는 조합은 m*n

Time complexity는 O(m*n), space complexity(m+n)이 됩니다

 

---

😍 Memoization 레시피 

 

1. Make it work

- Tree 기반 시각화해서 문제 쪼개기

- 재귀문(recursion) 사용해서 Tree 를 코드화 하기

- 이 단계까지는 Brute force approach이지만 테스트 해보기

 

2. Make it efficient

- memo 객체 만들기(key: def함수의 input 변수, value: return value)

- base case 를 memo value 로 담기

 

 

 

** 이 글은 freecodecamp의 Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges 강좌를 기반으로 정리된 글입니다. 강의 자체가 구성이 너무 좋고 예시도 풍부해서 보시길 추천드려요 :))

https://www.youtube.com/watch?v=oBt53YbR9Kk&t=179s&ab_channel=freeCodeCamp.org