[이.코.테] Chapter 08 다이나믹 프로그래밍

다이나믹 프로그래밍이란?

: 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

 

다이나믹 프로그래밍을 사용할 수 있는 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

탑다운(Top-Down) 방식

- 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다 하여 탑다운 방식이라 말한다.
- '하향식'이라고도 한다.
- 메모제이션은 탑다운 방식에 국한되어 사용

 

보텀업(Bottom-Up) 방식

- 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 말한다.
- '상향식'이라고도 한다.
- 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라 부른다.

메모제이션 기법

- 한 번 구한 결과를 메모리 공간에 메모해두고, 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 = 캐싱
- 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
- 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념
- 구현 예시) 한 번 구한 정보를 리스트에 저장, 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다.

 

다이나믹 프로그래밍 접근 방법

- 일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에(탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면(즉, 메모이제이션) 코드를 개선하는 방법
- 가능하다면 재귀 함수를 이용하는 탐다운 방식보다는 보텀업 방식으로 구현하는 것을 권장
∵ 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문