동적 계획법(Dynamic Programming, DP)

우리는 컴퓨터를 활용해도 해결하기 어려운 문제가 존재한다. 흔히 말하길, 해를 구하는 과정에서 비용( 시간 or 공간 )이 매우 많이 필요한 문제 등이 컴퓨터로 해결하기 어려운 문제,, 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 필요로 한다. 이때, 우리가 메모리 공간을 조금 더 할당함으로써 연산 속도를 증가시킬 수 있는 방법이 존재하는데 이것이 다이나믹 프로그래밍 기법이다.

---

동적 계획법은?

동적 계획법(다이나믹 프로그래밍)은 2가지 방식으로 접근할 수 있으며, 특히 메모이제이션기법을 통해 이전의 연산 결과를

저장하고 이를 다음 연산에 필요한 과정을 따른다.

 

모두 책에나 블로그에서 봤듯이 동적 계획법의 대표적인 예로 피보나치수열을 통해 알고리즘에 접근해보도록 하자.

 

 

피보나치수열

피보나치수열의 원리에 대해 간단히 얘기하면 이전 두 항의 합을 현재의 항의 값으로 설정하는 수열을 의미한다.

수열의 점화식을 다음과 같이 정의할 수 있다.

( 알고리즘에 대한 공부를 많이 해보면 우리가 수학 수업 때 들은 점화식이라는 용어를 많이 볼 수 있는데, 특히 DP 알고리즘에서 많이 사용하기 때문에 이를 유추할 수 있도록 연습이 많이 필요한 것 같다.)

 

$${a_n} = {a_{n-1}} + {a_{n-2}}, {a_1} = 1, {a_2} = 1$$

 

이를 해석하면 다음과 같은데,

• n번째 피보나치 수 = (n - 1) 번째 피보나치 수 + (n -2) 번째 피보나치 수
• 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1

이를 구현하면,

그러나, 이러한 알고리즘은 심각한 문제가 있는데, n이 커지면 커질수록 수행 시간이 기하급수적으로 증가한다.

시간 복잡도(빅오 표기법 이용)에 따르면, $O\{2^N\}$으로 지수 시간이 소요된다. 이러한 시간을 N에 조금 큰 수만 넣어보면 연산 시간이 오래 걸리는 구나라고 느낄 수 있다.

 

그렇다면?

우리는 이를 동적 계획법으로 접근한다면 이 문제를 해결할 수 있다. 동적 계획법으로 접근한다는

 

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 값은 그것을 포함하는 큰 문제에서도 동일한 값으로 사용된다.

 

라고 얘기할 수 있다.

 

이를 통해 다음과 같이 구현할 수 있다.

이번에 구현된 소스를 활용해 이전에 해봤던 값을 넣어 보면 바로 체감할 수 있을 것이다.

동적계획법을 통해 피보나치수열의 시간 복잡도는 $O\{N\}$이다. 이전보다 빠른 연산 결과가 나오는 것이다.

왜?

메모이제이션(Memoization) 기법, 이전 연산의 결과를 메모리 공간(여기서는 cache [])에 저장해 두고 다음 연산에서 이를 꺼내 사용하는 기법을 활용한 것으로, 이미 계산한 적이 있는지에 대해 조건문을 통해 확인하고 해당 값을 꺼내 사용할 수 있다.

 

접근 방법은?

동적 계획법은 두 가지의 접근 방식이 존재한다. 큰 문제 혹은 큰 값의 결과를 확인하기 위해 이보다 조금 작은 문제를 호출해서 이전 과정을 찾아보는 방식(탑 다운 방식), 작은 문제로 부터 점차 큰 문제로 넘어가기 위한 과정을 찾아보는 방식(바텀업 방식)이 있다.

 

탑 다운 방식

탑 다운 방식은 다른 말로 하향식 구조라고도 한다. 위에서 보았던 방식을 탑 다운 방식이라고 할 수 있다.

 

바텀 업 방식

바텀 업 방식은 다른 말로 상향식 구조라고도 한다. 아래 방식을 바텀 업 방식이라고 할 수 있다.