중복되는 부분 문제(Overlapping subproblems)

알고리즘을 풀때 주로 재귀(recursion)을 사용하는 경우, 중복되는 문제들이 생겨난다.
예를 들어 재귀를 이용해서 피보나치 수열, 팩토리얼 함수등을 구현할 때 중복되는 문제가 발생한다.
이는 입력값의 변화에 따라 연산을 실행할 때,
연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 따지는 시간 복잡도에 큰 영향을 끼친다.

memorization

이 부분을 해결하기 위해 다이나믹 프로그래밍중 한가지 방법인 memorization을 사용한다.
재귀의 아름다움(?)을 그대로 유지하면서 중복 연산을 제거하는 테크닉이다.
memorization은 캐싱(caching)을 이용해서 중복 계산을 방지하는 기법으로,
필요한 내용을 메모한다고 생각하면 된다.
이미 계산된 값은 테이블에 저장해둔다는 의미로 memorization을 tabling이라고도 한다.

memorization 예제: 피보나치 수열

피보나치 수열은 제 0항, 제 1항을 1로 제쳐두고 두 번째 항부터는
앞에 두 수를 더한 값을 결과로 두는 수열을 말한다.
피보나치 수열의 식은 다음과 같이 표현할 수 있다.
F(n) = F(n-2) + F(n-1)

function fibonachi(n){
  if (n === undefined) return ;
  if (n === 1 || n === 2) return 1;
  return fibonachi(n-2) + fibonachi(n-1);
}

fibonachi(30) // 832040
fibonachi(100) // ....

재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가지고 있어,
입력값을 40으로 두어도 수초가 걸리고, 100 이상이면 평생 결과를 반환받지 못할 수도 있다.
입력된 수가 커질수록 중복된 연산의 수가 수없이 불어나기 때문이다.
밑의 층으로 내려갈 수록 2의 n승 번씩 계산이 늘어난다.

앞서 설명한 memorization 알고리즘을 이용해 중복된 연산을 줄일 수 있다.
저장 장치를 만들어 연산을 할때마다 장치에 저장하고, 이미 계산 되어있다면,
그 값을 사용하는 방식이다.

let fibonachi = function (n) {
  if (n === undefined) return ;
  const memo = [0, 1];
  const memorization = (n) => {
    // 이미 해결한 적이 있으면, 메모해둔 정답을 리턴한다.
    if (memo[n] !== undefined) return memo[n];
    // 새롭게 풀어야하는 경우, 문제를 풀고 메모해둔다.
    memo[n] = memorization(n - 1) + memorization(n - 2);
    return memo[n];
  };
  return memorization(n);
};

fibonachi(30) // 832040
fibonachi(100) // 354224848179262000000

참고 사이트

https://www.youtube.com/watch?v=YNIasN6kT2M
https://helloworldjavascript.net/pages/255-fp.html
https://taesung1993.tistory.com/45
https://seungjuitmemo.tistory.com/22