[알고리즘] DP(Dynamic Progamming) 동적 계획법 / 피보나치수열

안녕하세요 감자코딩에 감자개발자 입니다. 벌써 일요일이 끝나고 월요일이네요.

저는 이번에 공부해볼 강의는 알고리즘중에 꽃이라고 할 수 있는 Dynamic Programming(동적계획법)에 대해서 공부하겠습니다.

1. 동적계획법이란 무엇인가?

간단히 말해서 큰문제를 작은문제로 나누어서 푸는 기법이라고 할 수 있습니다.

=(유사) 분할정복방법과 비슷합니다.

2. 동적 계획법의 대표적인 예

이항계수(nCr)의 계산이라고 할 수 있습니다.

3. 메모이제이션(memoization) 이란?

동적계획법에서는 중복을 막기위해서 저장된 값을 배열에 저장한 뒤, 다음 계산이 필요할때는 저장된 값을 불러와서 중복을 없애면 함수호출이 줄어들게 됩니다. 그러면, 시간복잡도도 훨씬 줄어들게 됩니다.

밑에 예제는 피보나치 수열에 관한 기본 예제를 가져와봤습니다.

* 피보나치수열

• 피보나치 수열은 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다 라고 정의되어있습니다.

• 밑에 있는 예제를 이해하기 위해서 가장 중요한것이 있습니다. F(n)으로 기준으로 삼아 예를 들겠습니다. F(0) = 1, F(1)=1, F(2) = 2 일경우 n=2 이고, F(n) = F(n-2) + F(n-1)의 점화식이 성립되게 됩니다.

• 하지만, 이 점화식이 다음 진행단계를 계속해서 진행될경우 어떻게 될까요? 그 다음 단계는 F(n+1) = F(n-1) + F(n)이 될것입니다. F(n+1) = 3, F(n-1) = 2, F(n) =1이 될것입니다.

• 겹치는 부분이 보이시나요? 연산 과정에 있어서 겹치는 부분이 계속해서 발생하게 됩니다. 이때 메모이제이션(Memoization)이라는 개념이 등장하게 됩니다. 잠시 저장해놨다가 그 필요에 따라 써먹겠다는 뜻입니다. 이 개념을 알고계시면 이해하시는데 좀더 수월하실겁니다.

4. TOP-DOWN 방식

재귀와 같은 방식으로 위에서 아래로 내려오는 방식입니다.

이때, 함수의 호출을 줄이기 위해서 memoization을 사용합니다.

(Recursive Call)

1 2 3 4 5

long long fib(long long n){     if (n == 1 || n == 2)   return 1;     return fib(n - 1) + fib(n - 2); } Colored by Color Scripter

cs

(DP방식-memoization 적용)

long long fib(long long n){
    if (n == 1 || n == 2)
        return 1;
    if (!memo[n])
        return memo[n];
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

5. 그러면 동적계획법은 언제 사용되는 것인가요?

동적계획법(DP)는 알고리즘의 최적값을 구할때 사용합니다.

6. 동적계획법(DP)의 동작 과정을 살펴봅시다.

(1) 몇차원 (=변수 개수) DP를 할 것인가?

(2) 변수의 개수가 정해졌으면 각각의 변수는 무엇을 의미하는가?

(3) DP값이 어떤 의미인가?

(4) 어떤 DP값과 다른 DP값의 관계가 있는가? 있으면 어떤관계인가?

(5) 4의 점화식을 사용하여 재귀 또는 for문 DP로 계산한다.

7. 동적계획법의 초기화

동적계획법에서는 memoization말고 중요한것은 바로 "초기화" 입니다.

이미 계산한 것을 다시 계산하지 않기 위해서는 계산한 것과 계산하지 않은 것의 차이가 있어야 한다는것 알아두세요.

*계산하지 않은 값은 초기값(초기화한 값) 그대로이고 계산한 값은 바뀌어있기 때문에 그것으로 구분되어집니다.

 따라서 동적 계획법에서 계산한 값의 범위를 대략적으로 알아내서 그 범위에 있지 않은 값으로 초기화를 해주어야 한다. 계산된 값이 0일수 있는 동적계획법의 경우에는 보통 -1(또는 무한대 값이라고 부르는 int_max)을 사용하고 계산된 값이 0일수 없는 경우에는 그냥 전역변수로 선언합니다.

 8. TOP - DOWN VS BOTTOM - UP

TOP - DOWN 방식 에 memoizationd을 했다는 가정하에 시간복잡도는 같습니다.  하지만 실제 걸리는 시간은 TOP - DOWN DP가 더 깁니다. 재귀 DP의 장점은 점화식 그대로 호출이 되기 때문에 형식/순서에 얽매이지 않습니다. for문 DP의 장점은 시간이 (조금은) 적게 걸린다는것입니다.

REFERENCE : http://coding-all.tistory.com/2

이상으로 DP 개념정리를 마치겠습니다. 감자 코딩에 감자개발자 였습니다. 감사합니다.