[알고리즘] 동적 계획법 Dynamic Programming

[ 동적 계획법 / Dynamic Programming ]

동적 계획법, 줄여서 DP라고 부른다.

다른 알고리즘처럼 쉽게 와닿지 않은 알고리즘이다. 예를 들어 그리디 알고리즘/ 탐욕 알고리즘 같은 경우 단어 자체가 와닿는다.

'아! 그리디! 게걸스럽게 지금 상황에서만 최적을 구하는 알고리즘이구나!' 라고 말이다.

하지만 동적 알고리즘, 쉽게 와닿지 않는다.

뭐가 동적이라는 거지? 그래서 동적이라는 뜻을 찾아 보았다.

더 모르겠다. 뭐가 기운차게 움직이는거지? 그래서 열심히 구글링을 했다.

I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, "Where did the name, dynamic programming, come from?" The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named . He was Secretary of Defense, and he actually had a pathological fear and hatred of the word "research". I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term research in his presence. You can imagine how he felt, then, about the term mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word "programming". I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

— Richard Bellman, Eye of the Hurricane: An Autobiography (1984, page 159)

영어가 너무 길어서 접은글로 표시 했지만, 간출여서 말하면 dynamic 이라는 단어가 그럴듯해서 선택했다고 한다.

그가 이름을 잘못지은 탓에 뒤에 공부하고 있는 학생들은 웁니다.

쨋든, 다이나믹 프로그래밍에 대해서 알아보자.

원리

다이나믹 프로그래밍은 아래와 같이 구분할 수 있다. ( 글쓴이 생각 )

1. 문제 세분화

2. 과거를 통한 값 추출 ( 점화식 )

아래 대표적인 예제인 피보나치 수열을 통해서 조금 더 자세하게 설명하고자 한다.

예제

백준 온라인 저지 피보나치 수열(링크클릭)을 참고하면 아주 좋을것 같아서 가져왔습니다.
[ 코틀린 소스코드 (링크클릭)]

피보나치 수열은 다음과 같다.

그럼 예시로 피보나치 5번째 F(5)를 구해보자.

F(5) = F(3) + F(4) 이다.

그럼 F(3) 과 F(4)를 각자 구한다. 그런 후에 오른쪽 밑에 F(3)은 아직 더 계산해야 함으로 F(3)을 한번더 구한다.

F(3)을 구하고 나니, 위의 그림처럼 보면 F(3) 을 2번 계산하게 된다. 

위의 처럼 F(5)를 구하기 위해서 5 부터 1까지 내려오는 방식을

TOP-DOWN

방식이라고 한다. 우리가 가장 쉽게 피보나치 수열을 구하는 방식이다.

하지만, 우리가 수기로 피보나치 수열을 구하는 방식을 보면 F(1)부터 위로 올라가며 최종 해를 구한다.

우리가 수기로 피보나치 해를 구하는 방식은 위와 같은 순서로 짜게 된다.

TOP-DOWN 방식과 반대로 처음부터 최종해까지 다가간다. 위와 같은 방식을

BOTTOM-UP

이라 한다. 다이나믹 프로그래밍은 BOTTOM-UP 방식을 주로 사용하게 된다.

피보나치 수열문제 해결에서 다음과 같은 방식을 사용했다.

F(5)를 구하고자 할때

1. F(N) = F(N-2) + F(N-1) 으로 문제를 세분화 했다.(점화식을 세웠다.)

2. 과거의 값(BOTTOM-UP 으로)을 사용했다.

메모제이션 - Memoization

피보나치 수열을 BOTTOM-UP 방식으로 해결할 때, 우리는 1에서 5로 가면서 각 피보나치 수열의 값을 저장하면서 F(5)까지 나아갔습니다.

이처럼 한 번 계산된 결과를 저장했다가 활용하는 방식으로 중복 계산을 줄이는 것을 메모제이션 이라고 합니다. 

글쓴이의 생각

다이나믹 프로그래밍 문제를 해결하다보면, 가끔 막막할 때가 있습니다.

주어진 문제가 다이나믹 프로그래밍인것 같긴한데 문제를 세분화하기 까다롭다고 생각될 때에는 아주 작은 값부터 시작하면,

점화식의 끝자락이 보이는 듯한 느낌이 듭니다. 가장 작은 값부터 문제 원리를 이해하며 값 몇개를 구하다보면 문제 세분화하는데 도움이 되는 것 같았습니다.

최초 작성일 : 2012-02-13