동적계획법은 문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용할 수 있는 알고리즘 설계 기법입니다. 동적계획법을 사용하면 불필요한 계산을 줄이고, 효율적으로 최적해를 찾을 수 있습니다.
동적계획법은 “전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식” 입니다.
- 전체 문제를 작은 문제로 단순화한다. -> 부분 문제를 정의한다.
- 재귀적인 구조를 활용할 수 있는 점화식을 만든다. -> 점화식을 만든다.
- 작은 문제를 해결한 방법으로 전체 문제를 해결한다. -> 문제를 해결한다.
- 메모이제이션(Memoization)은 동적계획법에서 아주 중요한 개념입니다. 함수의 값을 계산한 뒤 계산된 값을 배열에 저장하는 방식입니다. 이러한 메모이제이션은 필요한 때마다 함수를 다시 호출하지 않고 값을 빠르게 가져올 수 있습니다.
예시 문제 — 격자상의 경로
다음 문제는 n X n 격자가 있을 때 왼쪽 위부터 오른쪽 아래까지 갈 때에 가장 최적의 경로(최댓값을 갖는)를 찾는 문제입니다. 방향은 오직 오른쪽과 아래만로 가능합니다. 위와 같은 격자가 주어졌을 때 최적 경로를 찾는 것이 문제입니다.
해결 방법
- 부분 문제를 정의한다. -> 왼쪽 위를 (0,0), 오른쪽 아래를 (4,4)로 하는 좌표를 기준으로 sum이라는 새로운 2차 배열을 만든다. 새로 만들어진 sum에는 (y,x)좌표까지의 최댓값을 저장합니다.
- 점화식을 구한다 -> sum(y,x)는 sum(y,x-1) 이나 sum(y-1,x) 중에 큰 값을 골라서 원래 격자에 주어진 (y,x) 값을 더하면 (y,x) 좌표까지의 최댓값이 구해집니다. 점화식은
sum(y,x) = max(sum(y,x-1),sum(y-1,x)) + value(y,x)입니다. - 이중 for문으로 1부터 배열 길이 만큼 sum 배열을 채워 넣으면 sum(n,n)의 값을 구할 수 있습니다.
