다이나믹 프로그래밍(Dynamic Programming, 동적계획법)이란 뭘까요?

큰 문제를 작은 문제로 나누어서 푸는 방법을 다이나믹 프로그래밍이라고 합니다.

이름의 '다이나믹'과는 거리가 먼 방식입니다. 실제로 다이나믹 프로그래밍의 고안자 벨만은 dynamic이라는 단어를 그냥 멋있어서 선택했다고 합니다.

 

문제가 두 가지 속성을 만족해야 다이나믹 프로그래밍을 사용해 문제를 풀 수 있습니다.

  1. Overlapping Subproblem (겹치는 부분문제)
    : 큰 문제를 작은 문제로 쪼갤 수 있을 때, 동일한 작은 문제 겹치는 경우.
  2. Optimal Substructure (최적부분구조)
    : 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있을 때

다이나믹 프로그래밍으로 풀 수 있는 대표적인 문제로는 피보나치 수, 이항계수 등이 있습니다.

 

최적부분구조를 만족하기 때문에 정답을 한 번 구한 것을 저장해서 그 정답이 필요할 때마다 다시 계산하지 않고 메모해둔 것을 불러서 쓰면 되겠죠. 이것을 메모이제이션(Memoization)이라고 합니다.

메모이제이션을 적용할 수 있으려면 함수의 반환값이 그 입력값으로만 결정돼야 합니다. 이때 이 함수를 참조적 투명 함수(referential transparent function)라고 합니다.

 

구현 방식은 두가지 방법이 있습니다.

  1. Top-down
  2. Bottom-up

Top-down 방식은 재귀호출을 이용해 풀 수 있고, Bottom-up 방식은 반복문으로 풀 수 있습니다.

Bottom-up 방식은 해를 구하기 이전까지 모든 해를 구해야 하기 때문에 Top-down 방식보다 느릴 수도 있습니다. 하지만 Top-down 방식은 함수 호출스택을 이용하기 때문에 그 부분을 감안하면 일반적인 경우(모든 해를 구해야 하는 경우) 두 방식은 비슷하다고 볼 수 있을 것 같습니다.

반응형