Dynamic Programming

Dynamic Programming 동적 프로그래밍

복잡합 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

원리

• 문제를 여러 개의 하위 문제로 나누어 푼다. 그리고 그것을 결합하여 최종적인 목적에 도달한다.
• 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장한다. 나중에 같은 하위 문제가 나왔을 경우 간단히 해결가능하고 계산 횟수를 줄일 수 있다.
• 동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다.
• 단순한 재귀함수에 저장 수열(이전의 데이터를 모두 입력하는 수열)을 대입하는 것 만으로도 최적해를 구할 수 있는 동적 알고리즘을 찾을 수 있다.

피보나치 수열

// 피보나치 수열 (재귀 함수)
// fibo(0) = 0, fibo(1) = 1, fibo(n) = fibo(n-1) + fibo(n-2)
// 0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열
//n 은 자연수
function fib(n) {
	if (n == 0){
		return 0;
	} else if(n == 1) {
		return 1;
	}
	return fib(n-1) + fib(n-2);
}

예를 들어보자. 위와 그림은 7번째 피보나치 수를 구하는 과정이다. 7번째 값을 구하기 위해서는 5,6번째를 더해야 하기 때문에, 이 두 값을 구해야한다. 이렇게 5,6 번째 값을 구하는 것을 부분문제라고 한다. 이렇게 더이상 쪼개지지 않는 fib(0), fib(1)을 만날 때 까지 계속해서 쪼개지면, 부분문제가 중복이 된다. 이런 중복문제를 해결하기 위해서는 처음 풀었던 문제의 값을 저장하고 불러오면 된다. 그러면 반복 계산이 필요 없어진다. 이럴때 동적 계획법을 사용하면 아주 편리하다.

동적 계획법 풀이에서는 부분문제를 풀 때마다 그 값을 저장하는 저장소(cache) 를 만든다. 이런 동적 계획법을 사용하는 문제를 풀 때 사용할 수 있는 방법 중 하나는 반복문을 사용하는 반복적 풀이(iterative) 와 재귀 호출과 메모이제이션을 사용하는 재귀적 풀이(recursive)가 있다.

메모이제이션이란?
재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법.

function fibo_dp(n) {
      let cache = [];
      for(let i=0; i<n+1; i++){
        cache.push(i);
      }

      for(let i=2; i<n+1; i++){
        cache[i] = cache[i-1] + cache[i-2];
      }
      return cache[n];
}