[고급 알고리즘] Dynamic Programming

1. Dynamic Programming

• 큰 문제를 작은 문제로 나누어 풀되, 작은 문제의 결과를 저장해두고 재사용하는 알고리즘
• 나중에 같은 부분 문제를 계산하지 않도록 합니다

 

조건

조건명	정의	의미/핵심 포인트
Overlapping Subproblems	전체 문제를 나누면 동일한 서브문제가 반복해서 등장	같은 계산을 반복하지 않도록 Memoization하여 재사용
Optimal Substructure	전체 문제의 최적 해가 부분 문제들의 최적 해로 구성됨	부분 문제와 전체 문제 사이에 점화식 존재 ✅ 작은 문제 해결 ➡️ 이를 조합해 큰 문제 해결

 

예시) Overlapping Subproblems

피보나치 수열

• F(5)를 구하려면 F(4), F(3)이 필요
• F(4)를 구하려면 F(3), F(2)가 필요

 

예시) Optimal Substructure

최단 경로 문제

• A->D 최단 경로는 A->B, B->D 최단 경로의 합

 

풀이 방식

구분	Top-Down (Memoization)	Bottom-Up (Tabulation)
동작 방식	문제 해결 과정에서 하위 문제가 필요할 때만 계산하고, 그 결과를 저장하여 재사용	가장 작은 하위 문제부터 시작해 모든 경우를 순서대로 계산하며 DP 테이블을 채움
핵심 개념	지연 계산 (Lazy Evaluation)	선계산 (Eager Evaluation)
구현 형태	재귀 + 메모이제이션 (memo[])	반복문 + DP 테이블 (dp[])
장점	- 필요한 서브문제만 계산 → 불필요 연산 감소 - 코드가 직관적 (점화식과 구조가 유사)	- 모든 하위 문제를 정확히 계산함 (누락 없음) - 재귀 호출 오버헤드 없음 - 스택 오버플로우 위험 없음
단점	- 재귀 호출 비용 존재 - 입력이 크면 스택 오버플로우 발생 가능	- 필요 없는 하위 문제도 전부 계산 → 비효율 가능성 있음 - 구현이 직관적이지 않을 수 있음
추천 상황	- 실제로 필요한 값만 구하면 되는 경우 - 문제 구조가 재귀적으로 표현되기 쉬운 경우	- 입력 크기가 크거나 재귀가 위험한 경우 - 모든 경우를 구해야 하는 테이블 기반 문제(LCS, LIS 등)

 

2. 적용 과정

1. 분할: 주어진 문제를 작은 부분 문제로 나눕니다.
2. 점화식 도출: 각 부분 문제와 전체 해 간의 관계를 나타내는 수학적 식을 정의합니다.
3. 메모이제이션 테이블 정의
   1. dp 배열 정의: 부분 문제의 해를 저장할 자료구조를 정의합니다. (크기, 차수 등) 
   2. 인덱스 의미 정하기: dp 배열의 각 인덱스가 어떤 의미를 가질 지 정의합니다. (점화식과 밀접하게 연관됩니다)
   3. 초기값 정하기: 점화식의 계산을 시작하기 위한 초기값을 설정합니다. (반복적인 연산의 기점이 됩니다)
4. 부분 문제 해결 및 저장
5. 결과 재사용
6. 결과 조합 및 전체 해 도출

 

예시) 피보나치 수열

분할

• ✅ F(n) = F(n-1) + F(n-2)
• ➡️ 큰 문제 = 더 작은 문제들의 조합이 되는 패턴 찾기

 

점화식 도출

• F(n) = F(n-1) + F(n-2)

 

메모이제이션 테이블 정의

• 초기화: dp = new int[n]
• dp[i]: i번째 피보나치 수
• dp[0] = 0, dp[1] = 1

 

부분 문제 해결 및 저장

결과 재사용

결과 조합 및 전체 해 도출

dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]
return dp[n]

 

 

출처

• Wiki - 동적계획법
• Wiki - bottom-up and top-down
• BaaaaaaaarkingDog - Dynamic Programming