1. 동적계획법 (Dynamic Programming)

큰 문제를 작은 문제로 나누어 푸는 것

Divide and Conquer (분할 정복)과 비슷해 보이지만, 이와 다르게 Dynamic Programming (동적 계획법)은 작게 나눈 문제가 반복되는 특성을 활용합니다. 즉, 작은 부분 문제들이 여러 번 등장하지만 그 결과가 변하지 않는다는 점을 이용해 한 번 계산한 결과를 저장하고 재활용함으로써 효율적으로 문제를 해결합니다.

2. 조건 및 예시

동적계획법을 위한 두 가지 핵심 조건은 다음과 같습니다.

1. Overlapping Subproblems (중복되는 부분 문제)

• 같은 하위 문제가 여러 번 반복해서 등장함
• ex) 피보나치 수열에서 F(4)를 계산할 때 F(2)가 여러 번 계산됨 (한 번 계산한 F(i)값을 배열 등에 저장해두고 재사용!)

2. Optimal Substructure (최적 부분 구조)

• 전체 문제의 최적해가 하위 문제의 최적해로 구성될 수 있음
• ex) 최적 경로 문제에서 A->B->C의 최적해는 A->B와 B->C의 최적해를 합친 것

3. Top-down & Bottom-up

동적 계획법을 구현하는 두 가지 방식은 다음과 같습니다.

1. Top-down (메모이제이션, Memoization)
   재귀 + 메모이제이션 방식으로 큰 문제를 재귀적으로 풀다가, 이미 푼 하위 문제가 나오면 저장된 값을 사용합니다.

2. Bottom-up
   작은 문제부터 차례대로 해결하며 결과를 배열에 저장합니다. 재귀 호출 없이 반복문만 사용합니다.

사진 출처: Demystifying Dynamic Programming in Java: Bottom-Up and Top-Down Approaches Explained