동적 계획법

• 동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다.

✅ 동적 계획법의 핵심 이론

동적 계획법의 원리와 구현 방식

① 큰 문제를 작은 문제로 나눌 수 있어야 한다.

② 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다.

③ 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. 이를 메모이제이션기법이라고 한다.

④ 동적 계획법은 톱-다운 방식과 바텀-업 방식으로 구현할 수 있다.

• 동적 계획법의 가장 대표적인 문제인 피보나치 수열을 예로 들면,

피보나치 수열 공식

D[N] = D[N - 1] + D[N - 2] // N번째 수열 = N - 1번째 수열 + N - 2번째 수열

1. 동적 계획법으로 풀 수 있는지 확인하기

• 6번재 피보나치 수열은 5번째 피보나치 수열과 4번째 피보나치 수열의 합이다. 즉, 6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 4번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있고, 수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있다.

2. 점화식 세우기

• 점화식을 세울 때는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요하다. 이 예제는 피보나치 수열의 공식 자체가 점화식이므로 공식을 점화식으로 사용할 것이다. 즉, 피보나치 수열의 점화식은 D[i] = D[i - 1] + D[i - 2]이 된다.

3. 메모이제이션 원리 이해하기

• 메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용하는 것을 말한다. 다음 그림을 보면 위에서 2번째와 3번째 피보나치 수열은 맨 왼쪽 탐색 부분에서 최초로 값이 구해지고, 이때 DP테이블에 값이 저장된다. 이에 따라 나중에 2번째와 3번째 피보나치 수열의 값이 필요할 때 재연산을 이용해 구하지 않고, DP 테이블에서 바로 값을 추출한다. 이러한 방식을 사용하면 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측면에서 많은 이점을 가질 수 있다.