23 동적 프로그래밍

23.1 동적 프로그래밍

  동적 프로그래밍이란 복잡한 문제를 간단한 하위 문제의 모음으로 분리해서 각 하위 문제들을 풀어서 그 답을 저장하고 활용하는 방식으로 문제를 해결하는 문제 해결 방식이다. 즉, 문제를 해결하는데 사용할 수 있는 접근 방법 중 하나이다. 대부분의 문제를 동적 프로그래밍으로 해결 할 수는 없지만, 동적 프로그래밍으로 해결할 수 있는 문제들에 대해 동적 프로그래밍으로 문제를 해결하는 경우 성능에 있어서 아주 큰 차이를 가져온다. 다시 말해 대부분의 문제에 적용할 수 있는 것은 아니지만 사용할 수 있는 경우에는 코드의 속도를 정말 많이 올릴 수 있다.

 

23.2 동적 프로그래밍 활용 가능 상황

  동적 프로그래밍을 사용할 수 있는지를 확인하기 위해서는 두 가지 조건을 확인해야 한다.

1) 반복되는 하위 문제가 존재하는가?

2) 최적 부분 구조가 존재하는가?

 

  반복되는 하위 문제란 해결이 필요한 문제에 어떤 방식으로든 중첩되는 하위 문제들이 있어야 한다는 것이다. 이 말은 한 문제를 더 작은 문제들로 나눌 수 있고, 그 조각들 중 일부가 재활용 가능하다는 말이다. 각각의 조각이 다른 모습이면 안되고 여러 번 재사용할 수 있어야 한다. 대표적인 예로 피보나치 수열을 들 수 있다. 

 

  최적 부분 구조란 하위 문제의 최적 해답을 통해서 더 큰 범주의 문제의 최적 해답을 구성할 수 있는 경우를 말한다. 예를 들면 서울에서 부산을 가는 최단 경로를 구해야 한다고 해보자. 이 문제는 (서울에서 천안으로 가는 최단 거리) + (천안에서 부산으로 가는 최단 거리)로 하위 문제를 나눌 수 있고 각각의 하위 문제의 최단 거리들의 합이 (서울에서 부산으로 가는 최단 거리)가 되는 것을 말한다.

 

23.3 피보나치 수열

  일반 재귀 방식으로 피보나치 수열

 

◎피보나치 공식 

1) fib(n) = fib(n-1) + fib(n-2)

2) fib(2) = 1

3) fib(1) = 1

예를들어 fib(20)은 20번째 숫자의 값을 말하는 것이다.

fib(6)은 숫자 8을 의미한다.(1 + 1 + 2 + 3 + 5 + 8)

// 일반 재귀 방식의 피보나치 수열
function fib(n){
    if(n <= 2) return 1;
    return fib(n-1) + fib(n-2);
}

  위의 함수처럼 일반 재귀 방식으로 피보나치 수열을 작성할 수 있지만, O(2^N)의 시간 복잡도를 가지기 때문에 매우 비효율적이다. 조금만 전달하는 값의 클수록 처리 시간이 매우 오래걸린다. 이러한 문제를 해결할 수 있는 방법이 바로 동적 프로그래밍이다. 피보나치 수열의 경우 반복되는 하위 문제가 존재하고 최적 부분 구조를 갖기 때문에 동적 프로그래밍으로 해결할 수 있다.

(ex fib(5) = fib(4) + fib(3) = fib(3) + fib(2) + fib(2) + fib(1))

 

23.4 Memo에 값을 저장하는 방법(Memoization)

  위의 일반 재귀 방식의 피보나치 함수의 문제점을 해결하는 방법으로는 하위 문제를 해결하고 나온 값들을 기억해 두었다가 다시 활용하는 것이다. 예를 들면 fib(5)를 구할때는 fib(3)의 계산이 두 번 반복하게 되는데 처음 fib(3)을 계산했을때 이를 기억하고 다시 fib(3)을 계산해야할 때 미리 저장해 놓은 fib(3)의 값을 활용해서 빠르게 계산하는 것이다. 핵심은 보통 배열이나 객체로 데이터를 저장할 구조를 만든 다음 저장해 놓은 값들을 활용해야 한다.

function fib(n, memo=[]){
  if(memo[n] !== undefined) return memo[n]
  if(n <= 2) return 1;
  var res = fib(n-1, memo) + fib(n-2, memo);
  memo[n] = res;
  return res;
}

23.5 Memoization을 활용해서 피보나치를 구현했을 경우의 빅오 시간 복잡도

1) 일반 재귀형 피보나치 : O(2^N)

2) 메모이제이션을 통한 피보나치 : O(N)

 

23.6 Tabulation

  타뷸레이션은 루프와 같이 순환을 통해 작업한다. 메모이제이션과는 반대로 가장 작은 하위 문제를 푼 다음에 그 결과를 저장한다. 즉, 가장 바닥에 위치한 fib(1)부터 계산을 하면서 저장하고 이를 활용하며 올라가는 방식이다.

function fib(n){
    if(n <= 2) return 1;
    var fibNums = [0,1,1];
    for(var i = 3; i <= n; i++){
        fibNums[i] = fibNums[i-1] + fibNums[i-2];
    }
    return fibNums[n];
}