[알고리즘] 동적계획법(DP), 다이나믹 프로그래밍 개념정리

다이나믹 프로그래밍이란 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다.

DP 동적계획법이라고 한다.

 

하나의 문제를 딱 한번만 풀어 비효율적인 알고리즘을 개선시키는 방법이다.

 

큰 문제를 작은 문제로 나눌 수 있다.

작은 문제에서 구한 정답은 그것을 포함하는 큰 문에제에도 동일하다.

 

크고 어려운 문제가 있을면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것이다. 

이 과정에서 '메모이제이션(Memoization)이 사용된다.

이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환만 하면 된다.

 

가장 기본적인 예시로 피보나치 수열이 있다.

 

첫번째 코드를 보게되면 오로지 재귀함수로만 문제를 풀게되면 다음과 같은 코드가 나온다.

num = 8이라는 값이 들어가게되면 밑에 그림처럼 될것이다.  

이 그림도 전부가 아니라 밑으로 더 뻗어있다.

그렇다면 우리는 fibonacci(7)에는 한번, fibonacci(6)에는 두번, fibonacci(5)는 세번, fibonacci(4)는 5번,

3과,2와1은 더 많을것이다. 

만약 100이라면, 10000이라면?

이렇게 재귀를 돌리게 되면 수도없이 많은 계산을 해야한다. 

function fibonacci(num) {
  if(num <= 1) return num;
  return fibonacci(num-1) + fibonacci(num-2)     
}

 

하지만 동적 계획법을 사용하게 되면 단계가 단축되게 된다.

우리가 한번 계산한 숫자를 memoization 배열에 넣으면서 다음번에 그 문제를 해결할때 메모해둔 정답을 꺼내어 사용하면 된다.

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

    

 

위와 같이 해주면 이미 계산된 결과는 배열 memoization에 저장되어 한번 구한 값을 다시 구하는 일은 존재하지 않는다. 
DP, 동적계획법, 다이나믹 프로그래밍의 개념을 이해하고 많은 문제 풀어보자.

 

 

출처

https://www.youtube.com/watch?v=FmXZG7D8nS4&t=415s