동적 계획법

동적계획법(Dynamic Programming)?

문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용할 수 있는 알고리즘 설계 기법.

동적 계획법을 사용하면 불필요한 계산을 줄이고, 효율적으로 최적해를 찾을 수 있다.

즉 전체 문제를 작은 문제로 단순화한 다음 점화식을 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식이다.

처음 주어진 문제를 더 작은 문제들로 나눈 뒤 작은 문제들의 답을 구한 후 원래 문제에 대한 답을 계산한다는 점에서 분할 정복과 비슷하다.

하지만 동적 계획법에서는 작은 문제들이 중복될 수 있지만, 분할 정복은 중복될 수 없다는 점이다.

다시 말해 동적 계획법과 분할 정복의 차이는 문제를 나누는 방식이다. 동적 계획법에서 어떤 작은 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 저장하여 재활용해서 속도를 향상시킬 수 있다. 이때 이미 계산한 값을 저장해 두는 메모리를 캐시라고 하며, 두 번 이상 계산되는 작은 문제를 중복되는 부분 문제(overlapping subproblems)라고 부른다.

부분 문제를 정의
점화식 생성
해결

메모이제이션(Memoization)?

메모이제이션은 동적계획법에서 중요한 개념으로, 이미 계산된 값을 저장하여 필요할 때마다 값을 다시 계산하지 않고 저장된 값을 가져올 수 있다.

조건

두 가지를 만족해야 동적 계획법으로 문제를 풀 수 있다.

Overlapping subproblem: 겹치는 부분 문제
Optimal Substructure : 최적 부분 구조

1. Overlapping Subproblem

겹치는 부분 문제는 어떤 문제가 여러개의 부분문제로 쪼개질 수 있을 때 사용하는 단어이다. 이 부분 문제는 새로운 부분 문제를 생성하기보다는 여러번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제를 말한다.

피보나치 수열이 위에 해당한다. (앞의 두 수를 더하면 다음 수가 된다)

이때 문제와 작은 문제는 다음과 같이 될 것이다.

문제 : N번째 피보나치 수를 구하는 문제
작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

2. Optimal Substructure

최적 부분구조는 어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 설계될 수 있는 경우를 말한다.

즉 최적 부분구조일 때 문제의 정답을 작은 문제의 정답에서부터 구할 수 있다.

피보나치를 다시 보자.

10 번째 피보나치 수를 구할 때는 예를 들어 2번째 피보나치 수를 이용해야 한다. 9 번째도 마찬가지이고, 2번째 피보나치 수를 여러번 이용해야 한다. 하지만 매번 2번째 피보나치 수를 매번 계산하는 것은 비효율적이다.

이를 해결할 수 있는 방법이 위에서 언급했던 메모이제이션이다.

메모이제이션

동적 계획법에서 각 문제는 한 번만 풀어야 한다. Optimal Substructure를 만족하기 때문에 같은 문제는 구할 떄마다 정답이 가타. 따라서 정답을 한 번 구했으면 그 정답을 캐시에 메모해놓는다.

이것을 코드로 구현할 때는 배열에 저장하는 것으로 할 수 있다.