[알고리즘] 동적 계획법(Dynamic Programming) - 1

동적 계획법(Dynamic Programming)

우리가 전에 피보나치 수를 계산하기 위해 재귀 함수를 사용했었다.

이는 같은 연산이 반복되기 때문이다.

 그러나 이 함수의 진행 과정을 살펴보면 중복이 심하다는 것을 알수 있다.

위의 그림에서 보면 fib(2)가 여러번 반복되며 오버헤드가 증가함으로 결국 비효율적인 코드가 된다.

따라서 이러한 중복을 제거 하기 위해서 메모이제이션(Memoization)이라는 테크닉을 사용한다.

이는 사전에는 나오지 않는 프로그래밍 테크닉이며, 계산된 값을 버리지 말고 저장한다는 뜻이다

예를 들어 위의 그림에서 계산이 된 fib(2) 값을 저장해 놓고 있다가, 필요한 경우 계산없이 호출하게 된다.

이렇게 저장되는 배열을 '캐시'라고 하며, 중간에 저장하는 걸 '캐싱한다'라고 부른다.

따라서 위의 그림에서 처럼 배열 f를 캐싱용으로 하나 만들어 둔다.

이 배열 내부를 -1로 모두 초기화 시키고, 만약 -1이라면 결과값이 저장되어 있지 않으므로 계산을 실행한다.

이렇게 되면 어떤 경우에도 동일한 피보나치를 2번 실행하는 경우가 없다.

중복된 계산을 피하는 또 다른 방법으로는 Bottom up 이 있다.

재귀 함수가 Top down 임에 반해, Bottom up은 f(1)부터 f(n)까지 올라 오는 것을 의미한다.

이 방식의 핵심은 아래에서 부터 올라가기 때문에 f(n)을 구하기 위해 f(n-1)과 f(n-2)을 계산해야한다.

따라서 가장 기본적인 값으로 특정한 값을 계산 하려고 하는것을 Bottom up이라고 한다.

이렇게 Bottom up방식으로 계산하는 테크닉을 다이나믹 프로그래밍이라고 한다.

물론, 이는 다이나믹 프로그래밍을 좁은 의미로 해석할때 사용하는 방법이지만

가장 많이 사용되는 방법중에 하나이기도 하다.

두번째 예로, 이항 계수를 구하는 알고리즘이다.

이항 계수는 n개 중에 k개를 선택하는 경우의 수를 구할 때 사용한다.

보통 n!/(n-k)!*k!로 계산을 하지만, 이렇게 할 경우 많은 계산이 중복된다.

또한 계산의 범위가 커질 경우 오버플로우가 생길수도 있다.

때문에 이렇게 하는 대신, 위의 그림의 공식을 사용하도록 한다.

물론 n=k일때거나 k=0일때 1을 반환하도록 한다.

그래서 이를 계산 할 때, 위와 같은 재귀 코드를 사용해서 계산하면 된다.

이렇게 재귀 함수를 반복하다보면 언젠가 n이 k와 같아지거나 k가 0이 되는 base case에 도달하게 된다.

따라서 이항계수의 답을 찾게 된다.

그러나 이와 같은 재귀 계산에서도 같은 값에 대해 중복되는 코드가 많아지므로

메모이제이션 기법을 사용하면 훨씬 빠르고 강력한 계산이 가능하게 된다.

앞서 말한것과 마찬가지로 -1로 모든 캐시 배열을 초기화 해주며,

-1일 경우 계산을 진행하고, 아닐경우 해당 인덱스의 배열값을 호출 한다.

마찬가지로 이를 Bottom up 방식으로 계산을 한다면 위의 그림과 같은 결과가 나온다.

2차원 배열이라서 어디가 Bottom up인지 생각할수 있지만, Bottom up이란 위치가 바닥에서 부터가 아니라

기본적인 값에서 부터 출발한다는 뜻이된다.

따라서, 순환식에서 기본적인 값을 토대로 계속 정답까지 값을 구하므로 재귀가 필요없고 중복된 값도 제거된다.

메모이제이션과 다이나믹 프로그래밍의 특징은 다음과 같다.

1) 메모이제이션이나 다이나믹 프로그래밍 둘다 순환식을 계산하는 방법이라고 할 수 있다.

2) 모두 동적 계획법의 일종이라고 보기도 한다.

3) 메모이제이션은 Top down 방식이고 실제 필요한 sub problem을 푼다, 

4) 다이나믹 프로그래밍은 Bottom up 방식이며 재귀에 수반되는 overhead가 없다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘