동적 계획법(Dynamic Programming)

동적 계획법: 하나의 문제를 여러 작은 문제로 나누고, 작은 문제의 결과를 저장하여 큰 문제를 해결한다. 

• 하나의 문제를 여러 개의 하위 문제로 나눈 다음, 결합하여 답을 도출한다.
• 하위 문제들의 결과를 저장한다.(Memoization, 메모이제이션) -> 동일한 문제가 나왔을 때 저장해둔 결과를 가져다 쓰며, 실행속도 빠르게 한다.

1. 겹치는 부분 존재
   • DP는 작은 문제의 결과를 저장하고 재사용하여 문제를 푼다. 따라서, 동일한 작은 문제가 있을 때 사용한다. 
2. 최적 부분 구조
   • 작은 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 
   • 작은 문제에서 구한 최적의 결과가 큰 문제에서도 동일하게 최적으로 적용되는 경우이다.

 

 

동적계획법의 가장 대표적인 피보나치 수를 구현해보자!

피보자치 수열은 0번째 항이 0, 1번째 항이 1일 때, 모든 항이 바로 앞 두 항의 합인 수열이다.

즉, f(n) = f(n-1) + f(n-2) 이다.

 

만약, f(4)를 구할 때 아래와 같이 표현할 수 있다.

출처: https://velog.io/@sinclairr/boj-2749

 

이처럼 피보나치 수를 구하기 위해

1. 여러 작은 문제로 분할할 수 있으며, 작은 문제의 값을 저장해두고 재사용하여 문제를 풀 수 있다.

    큰 문제: f(n) 구하기

    작은 문제: f(n-1), f(n-2) 구하기

    큰 문제: f(n-1) 구하기

    작은 문제: f(n-2), f(n-3)구하기

2. 작은 문제의 결과 값으로 큰 문제의 결과를 도출할 수 있다. 

=> 문제 해결에 DP사용 적절!

 

DP는 2가지 방식으로 구현할 수 있다.

1) Bottom-Up(Tabulaiton(도표)방식) - 반복문 사용

    밑에서부터 값을 계산하고, 리스트에 값을 기록한다.

function solution_repeat(n) {
  let fiboArr = new Array(n);
  fiboArr[0] = 0;
  fiboArr[1] = 1;
  for (let i = 2; i <= n; i++) {
    fiboArr[i] = fiboArr[i - 1] + fiboArr[i - 2];
  }
  return fiboArr[n];
}

2) Top-Down방식(Memoization방식) - 재귀 사용

    위에서 부터 값을 계산하고, cache에 값을 기록하여 중복 계산을 방지한다.

function solution_recursive(n) {
  let fiboArr = [0];
  let fiboFunc = (n) => {
    if (n < 3) {
      fiboArr[n] = 1;
    }
    if (!fiboArr[n]) {
      // 피보나치 수가 없다면 연산
      fiboArr[n] = fiboFunc(n - 1) + fiboFunc(n - 2);
    }
    return fiboArr[n];
  };
  return fiboFunc(n);
}

 

 

참고)

https://leeiopd.tistory.com/entry/DP-Memorization-%EA%B3%BC-Tabulation

https://bit.ly/3T4Eavt

https://hongjw1938.tistory.com/47