동적 계획법(Dynamic Programming)

다이나믹 프로그래밍(dp)원리 동적 계획법 활용 피보나치 수열

다이나믹 프로그래밍(dp)

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

원리

문제를 여러 개의 하위 문제로 나누어 푼다. 그리고 그것을 결합하여 최종적인 목적에 도달한다.

각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장한다. 나중에 같은 하위 문제가 나왔을 경우 간단히 해결가능하고 계산 횟수를 줄일 수 있다.

동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다.

단순한 재귀함수에 저장 수열(이전의 데이터를 모두 입력하는 수열)을 대입하는 것 만으로도 최적해를 구할 수 있는 동적 알고리즘을 찾을 수 있다.

출처 : https://ko.wikipedia.org/wiki/동적_계획법 (위키백과)

동적 계획법 활용

피보나치 수열


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

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n-1) + fib(n-2)


//Javascript 코드
function fib(n) {
		if (n == 0){
				return 0;
		} else if(n == 1) {
				return 1;
		}
		return fib(n-1) + fib(n-2);
}

피보나치 수열을 코드로 옮겼을 때 위와 같이 매우 단순하다. 하지만 이 구조는 컴퓨터가 풀어내기에 비효율 적이다. 자연수 n 이 커질 수록 지수적으로 계산량이 증가하기 때문이다. 만약 n이 100이면 우리는 100번째 피보나치 수를 구하기까지 오랜 시간과 반복적인 계산을 계속 하게 될 것이다.

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

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

재귀적 동적 계산법


def fibo_dp(num):
    cache =  [ 0 for index in range(num + 1) ]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]


fibo_dp(7)


Out[-]
13


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

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

console.log(fibo_dp(7)); //13