[알고리즘] - 동적 계획법

동적 계획법이란

Dynamic Programming 이라고 부르며, 해결한 작은문제로 큰문제를 해결해 나가는 문제 풀이방식이다.

메모리를 많이 사용하는 대신 빠른 성능이 장점이다.

메모이제이션과 타뷸레이션 방식을 사용하여 문제를 해결한다.

메모이제이션이란

동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법이다

타뷸레이션이란

메모이제이션과 비슷하지만, 값을 미리 계산해둔다. 즉, 메모이제이션이 결과가 필요해질 때 계산한다면(Lazy-Evaluation) 타뷸레이션은 필요하지 않은 값도 미리 계산해둔다(Eager-Evaluation)는 차이가 있다. 초기화 오버헤드가 있지만 일단 계산해둔 값은 시간복잡도가 상수 시간(O(1))이 된다.

동적 계획법의 대표적인 예로는 피보나치 수열이 있다.

피보나치 수열

수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

피보나치 수열로 n 번째 값을 알아내기 위해선

n = (n -2) + (n -1) 로 값을 표현할 수 있는데,

1번째값과 2번째값을 각각 1,2 로 지정하여 n 번째 값을 도출해 낼 수 있다.

이 처럼 해결한 작은문제를 메모리에 저장해두어 큰 문제를 해결 할 수 있다.

function solution(n) {
  let dp = []
  dp[1] = 1
  dp[2] = 2
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}