다이나믹 프로그래밍 (Dynamic Programming)

Goal

1. 다이나믹 프로그래밍 이해하기
2. Top-down과 bottom-up 방법 알아보기

 

다이나믹 프로그래밍(Dynamic Programing)이란?

다이나믹 프로그래밍이란 어떤 문제가 주어졌을 때 그 문제를 더 작은 단위의 문제들로 쪼개서 작은 문제부터 풀어나가는 방법이다. 더 작은 단위로 쪼개진 문제를 풀어서 얻은 결과로 원래 문제의 해답에 점점 더 가까워지는 방식이다. 이 알고리즘의 헛점은 문제를 작은 단위로 쪼갤 수 있을 때만 사용할 수 있다는 것이다.

 

다이나믹 프로그래밍 알고리즘을 사용하는 가장 흔한 예제가 바로 피보나치 숫자이다. 피보나치 숫자는 그 전에 오는 두 숫자를 계속해서 더해 나가기 때문에 n번째 숫자를 알아내기 위해선 처음부터 계속 더해오면 된다. 두 숫자씩 더하는 작은 단위의 문제를 풀다보면 n번째 숫자를 구하기 위한 식에 언젠가는 도달할 수 있는 것이다!

 

자리	F[0]	F[1]	F[2]	F[3]	F[4]	F[5]	...	F[n]
숫자	0	1	1	2	3	5	...	F[n-1] + F[n-2]

 

Top-down vs. Bottom-up

Top-down (memoization)

Top-down은 memoization 기법을 사용하는 것이다. Memoization이란 작은 단위의 문제들의 결과를 저장해서 이 결과가 필요할 때 다시 계산할 필요 없이 바로 저장한 결과를 가져다 쓸 수 있는 것을 말한다. Top-down은 중간 단계를 저장하면서 진행하는 재귀함수와 같다.

 

위에서 설명한 피보나치 숫자를 top-down 방식으로 푼다면 아래 그림처럼 색이 칠해진 부분은 겹치기 때문에 한번만 계산해 놓으면 그 이후에 필요할 때는 계산 없이 미리 저장해 놓은 값을 갖다 쓰면 된다.

Top-down (memoization) 방식

 

Bottom-up (tabulation)

Bottom-up은 tabulation이라고도 불리는데 가장 작은 단계부터 차례대로 쌓아 올려가는 것이다. 피보나치 숫자를 풀 때 아래처럼 Fib(0) 과 Fib(1)이 각각 0과 1로 시작하는 것을 이용해 순서대로 Fib(2)를 계산하고, 저장된 값들로 Fib(3)을 계산하는 방식으로 진행한다.

Bottom-up (tabulation) 방식

 

Top-down과 Bottom-up의 차이

차이점	Top-down (memoization)	Bottom-up (tabulation)
알고리즘	재귀 방법 (recursive)	반복문 (iterative)
속도	재귀 방법을 이용하기 때문에 조금 더 느림	반복문이여서 n 개수 만큼 늘어남
진행 방향	풀고자 하는 문제에서 시작해서 base case (피보나치 예제에서 Fib(1)과 Fib(0))로 내려감	Base case에서 시작해서 풀고자 하는 문제로 올라감
공간 활용	재귀 방법이여서 n 개수가 크면 stack overflow가 발생해 코드가 중단됨	반복문이여서 문제 없음

 

 

참고

https://www.spiceworks.com/tech/devops/articles/what-is-dynamic-programming/

https://www.enjoyalgorithms.com/blog/top-down-memoization-vs-bottom-up-tabulation