동적 계획법 (Dynamic Programming) 이란?

enoch·2020년 11월 3일

알고리즘 이론

목록 보기

1/1

동적 계획법은 수학자인 리처드 벨만이 1940년대에 사용하던 용어입니다.
큰 문제 안에 작은 문제가 중첩되어있는 문제를 해결하는 데 사용하는 방법을 '동적계획법'이라고 이름 붙였다고합니다.

동적 계획법과 Dynamic이라는 단어는 어떤 연관성이 있는가 궁금했는데, 그 이유는 벨만의 자서전에서 찾을 수 있습니다.

알고리즘의 '시가변적이며 다단계적인' 특성을 나타내기 위해서 Dynamic이라는 단어를 채택했다고 합니다.

벨만이 정의한 것처럼 큰 문제 안에 작은 문제가 중첩되어있는 문제를 해결하는 것이 동적계획법입니다.

때문에 동적 계획법으로 문제를 해결하는것의 핵심은 문제를 일반화 하는 것이 됩니다.

한마디로,

동적계획법(Dynamic Programming)이란, 큰 문제를 작은 문제로 나누고, 작은 문제를 통해 문제를 일반화 시켜 전체 문제를 해결하는 방법입니다.

작은 문제를 일반화하는것이 무엇인가? 라고 질문하면.
대답은 간단합니다. 재귀적인 구조로 활용할 수 있는 점화식을 구하는 것입니다.

수학에서 문제를 일반화 할 때 점화식을 구한다. 프로그래밍에서도 이와같은 방법으로 점화식을 구하고 문제를 일반화 할 수 있다.

function fib(n)
 if n = 0
  return 0
 else if n=1
  return 1
 else
  return fib(n-1) + fib(n-2)

일반적으로 피보나치 수열을 구하는 함수는 위와 같습니다.
fib(4)를 구하려고 한다면 계산은 다음과 같습니다.

fib(4)
fib(3) + fib(2)
(fib(2) + fib(1)) + (fib(1) + fib(0))

세번 째 계산에서 fib(1)이 두번 계산되면서 계산 시간이 증가합니다.
만약 fib(n)에서 n이 40이상 큰 수가 된다면 계산 시간은 기하급수적으로 증가하게 됩니다.

생각해보면 fib(40)을 구하기 위해서 fib(3)은 무수히 많이 호출되어야 합니다. 이것이 시간 낭비입니다.

여기서 메모지네이션이 필요합니다.

메모이제이션은 함수의 값을 계산한 뒤 계산된 값을 배열에 저장하는 방식입니다. 필요할 때마다 함수를 따로 호출하지 않고 배열에서 값만 빠르게 가져올 수 있게합니다.

다시 피보나치로 돌아가서 만약 한번 계산한 fib(3)의 값을 배열에 저장해놓는다면 fib(3)을 호출하지 않고 값을 fib(3)의 값을 가져올 수 있게됩니다.
즉, f(n)을 구하는데는 O(N)의 시간이 필요합니다.

한번 계산한 값을 다시 계산하지 않는다.

이것은 문제 해결 시간을 엄청난게 단축할 수 있습니다.

🍣 초밥을 사랑하는 백엔드 개발자 입니다 :)