[기초 개념] Dynamic Programing(동적 계획법)

Dynamic Programing

Dynamic Programing(DP)는 복잡한 문제를 작은 부분 문제(sub problem)로 나누고,

그 결과를 저장하여 재활용하는 방식으로 문제를 푸는 알고리즘 기법이다.

 

즉, DP는 큰 문제를 작은 부분 문제로 쪼개고, 그 답을 저장해가면서 큰 문제를 푸는 방법이다.

 

---

DP가 필요한 이유

단순 재귀의 한계 (중복 계산)

같은 부분 문제를 여러 번 푸는 비효율 → 예: 피보나치 수열에서 fib(3)이 중복 호출 됨.

 

시간 복잡도 개선

DP를 쓰면 한 번 계산한 결과를 저장해서 O(N) 수준으로 줄일 수 있음.

 

---

 

DP의 두 가지 핵심 조건

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

큰 문제를 해결하는 과정에서 동일한 작은 문제가 반복적으로 등장해야 함.

 

최적 부분 구조 (Optimal Substructure)

큰 문제의 최적해가 작은 문제들의 최적해로 구성될 수 있어야 함.

 

---

 

DP 접근 방식

Top-down (재귀 + 메모이제이션)

큰 문제에서 시작해 재귀적으로 작은 문제로 내려가면서, 계산한 결과를 메모리에 저장.

 

Bottom-up (반복문 + 테이블)

작은 문제에서 차근차근 쌓아 올리며 테이블에 기록 → 반복문 기반이라 더 효율적.

 

---

DP 문제를 푸는  3단계

1. 상태 정의: dp[i]가 무엇을 의미하는지 정의.

2. 점화식 세우기: dp[i] = ... dp[i-1] ... dp[i-2] ... 같은 규칙 도출.

3. 초기값 설정: dp[1], dp[2]처럼 가장 작은 문제의 해를 명확히 두기.

 

.

.

 

 

DP로 접근할지 판단하는 법

부분 문제가 반복되는가?

최적 부분 구조가 존재하는가?