동적 계획법(DP)

동적 계획법이란?

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

동적 계획법의 핵심 이론

구현 방식

1. 큰 문제를 작은 문제로 나눌 수 있어야 함
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 함
3. 모든 작은 문제들을 한 번만 계산해 DP 테이블에 저장하며 추후 재사용 시 DP 테이블을 이용(메모이제이션(memoization) 기법)
4. 톱-다운 방식과 바텀-업 방식으로 구현할 수 있음

대표 문제

피보나치 수열

피보나치 수열 공식 : D[N] = D[N - 1] + D[N - 2]
(N번째 수열 = N - 1번째 수열 + N - 2번째 수열)

1. 동적 계획법으로 풀 수 있는지 확인
2. 점화식 세우기 : 점화식을 세울 때는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악
3. 메모이제이션 원리 이해 : 메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고, DP 테이블의 값을 이용하는 것

4. 톱-다운 구현 방식 이해 : 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀 함수 형태로 코드를 구현(가독성이 좋고, 이해하기가 편하다는 장점)
5. 바텀-업 구현 방식 이해 : 가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식

• 두 방식 중 좀 더 안전한 방식은 바텀-업
• 톱-다운 방식은 재귀 함수의 형태로 구현돼 있기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러 발생할 가능성
• 이 부분을 제외하면 두 방식의 차이점은 거의 없음