[알고리즘] DP 뿌시기...(1)

Dynamic Programming이란?

1.동적계획법이라고 불리며 특정 알고리즘이 아닌 '문제 해결 방식'을 말함.
2.해결한 작은 문제로 큰 문제를 해결하는 방식을 이야기함.
3.해결방식에 따라 메모리를 많이 사용하기도 하지만, 빠른 성능을 자랑한다.
4.메모제이션(Memoization)방식과 타뷸레이션(Tabulation)방식이 있다.
5.Dynamic하지도 않고 Programming이랑 관련도 없다. 단지 만든놈이 이름을 이렇게 만들었다.

알고리즘 문제를 해결할 때 효율성을 극대화해야할 때가 있다. 시간복잡도(big-O)의 해결이 주가 되는 문제들을 접할땐 단순 해를 구하기 위한 코드로는 절대 통과하지 못할 때가 있다. 그럴때는 여러가지 방법으로 해결하는데 그중 대표적인 문제중 하나가 DP의 메모이제이션이다.

피보나치수열이야말로 이전값(작은 문제)들을 통해 그 다음 값(큰 문제)를 해결하는 방식의 대표적인 예이다. f(n) = f(n-1) + f(n-2) 피보나치 수열을 만약 재귀로 접근하게 된다면, 아래와 같이 중복된 연산값을 계속해서 계산해야하는 일이 벌어진다.

---

이런경우 메모이제이션을 활용할 수 있는데, 새로 나온 f(n)의 값을 변수로 저장한다면, 그 다음 해를 구하는데 사용할 수 있다.

function solution(n) {
    if(n === 1) return 1;
    let f0 = 0n;
    let f1 = 1n;
    let f2 = 0;
    
    for(let i = 2; i<=n; i++){
        f2 = f1 + f0
        f0 = f1
        f1 = f2;
    }
    return f2 % 1234567n
};

(프로그래머스 - 레벨2 피보나치수열)

---

'타뷸레이션'을 활용한 문제는 아래와 같다.

function solution(n){
  let num = 1;
  const n2 = [], n3 = [], n5 = [];
  
  for(let i = 1; i<n; i++){
    n2.push(num * 2);
    n3.push(num * 3);
    n5.push(num * 5);
  
    num = Math.min(n2[0], n3[0], n5[0]);
    if(num === n2[0]) n2.shift();
    if(num === n3[0]) n3.shift();
    if(num === n5[0]) n5.shift();
  };
  return num;
};

이 경우 각각의 배열에 결과값들을 구해놓은 후 수열에 다음 수에 필요한 것들을 원할때 골라서 쓰는 방식이다.

---

정리해보자면 두 방법은,

타뷸레이션 => 미리 구해놓고 원할때 사용하는 방식.
메모이제이션 => 원할때 구해서 쓰는 방식.

타뷸레이션 방식은 해를 구할때 편하게 쓸수 있지만, 보다시피 미리 구해놓는 과정에서 효율성이 떨어질 수 있다.

---