[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming, 동적 계획법)

DP란 ‘하나의 문제는 단 한 번만 풀도록 하는 알고리즘’

다이나믹 프로그래밍은 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법
이미 진행이 되었던 연산이 반복되는 결점을 보안하기 위해 고안함.
=> 여러개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 여러개의 소문제로 분할 가능

다음 2가지 조건을 만족할 때 사용 가능

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

위 조건을 만족하는 대표적인 문제가 피보나치 수열
(피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합)
피보나치 수열의 점화식 : D[i] = D[i-1] + D[i-2]

<재귀함수를 이용한="" 피보나치="" 수열="" 구현="">

<반복문을 이용한="" 피보나치="" 수열="" 구현="">

동적 계획법

1. Memoization (Top-Down, 하향식)

하향식(Top-Down) 경우 하위 문제에 대하여 정답을 계산했는지 확인해가며 문제를 자연스럽게 풀어가는 방법 < 동일 계산 반복시 >
이전 계산값을 메모리에 저장하여 (메모리 공간을 약간 더 사용) (캐싱이라고도 함)

1. Tabulation (Bottom-up, 상향식)

최초 값부터 차례대로 계산해 나가는 방식