다이나믹 프로그래밍(Dynamic Programming)이란?
DP는 복잡한 문제를 작은 하위 문제로 나누고, 이를 이용해서 더 큰 문제를 해결하는 알고리즘 설계 기법
하위 문제들이 겹치기 때문에 한 번 해결된 문제는 다시 계산하지 않고 저장해 두고 재사용한다는 점에서 시간 복잡도가 크게 줄어든다.
💡 DP의 핵심 개념
DP를 적용하기 위한 2가지 요건:
- 중복 부분 문제 (Overlapping Subproblems): 동일한 하위 문제가 반복해서 나타나는 경우.
- 최적 부분 구조 (Optimal Substructure): 문제의 최적해가 하위 문제의 최적해로부터 결정될 수 있는 경우.
1. 중복 부분 문제 (Overlapping Subproblems)
-
동일한 하위 문제가 여러 번 반복되기 때문에, 중복되는 계산을 피하기 위해 한 번 계산한 값을 저장해 둔다.
-
점화식(Recurrence Relation)이란?
하위 문제 간의 관계를 정의하는 수학적 식.
- 예를 들어, 피보나치 수열의 점화식
F(n) = F(n-1) + F(n-2)은 문제F(n)이 하위 문제F(n-1)과F(n-2)로 나뉜다는 것을 나타낸다.
- 예를 들어, 피보나치 수열의 점화식
-
메모이제이션(Memoization)이란?
점화식에 기반한 하위 문제들의 중복 계산을 방지하기 위한 기술이다.
- 이미 계산된 하위 문제의 결과를 배열이나 딕셔너리에 저장해 두고, 동일한 하위 문제가 다시 발생할 때 저장된 값을 재사용한다.
- 즉, 메모이제이션은 점화식을 활용한 최적화 기법으로, 불필요한 중복 계산을 제거하여 성능을 높인다.
2. 최적 부분 구조 (Optimal Substructure)
- 문제의 최적해는 부분 문제들의 최적해로부터 결정된다.
- 즉, 전체 문제의 해가 각 부분 문제의 해로 나눌 수 있다는 점에서 최적 부분 구조를 가진다고 할 수 있다.
🔍 DP의 두 가지 접근 방식
피보나치 수열 문제를 통해 DP의 두 가지 접근 방식에 대해서 알아보자.
1. Top-down (Memoization)
재귀적으로 큰 문제를 작은 문제로 쪼개고, 각 문제의 답을 메모이제이션을 통해 저장하는 방식
public static long fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (memo[n] != 0) return memo[n]; // 이미 계산한 값은 재사용
memo[n] = fib(n - 1) + fib(n - 2); // 재귀 호출
return memo[n];
}- 큰 문제를 재귀적으로 나누고, 중복되는 계산을 방지하기 위해 계산된 값을 저장.
- 필요한 부분만 계산하므로 효율적이지만, 재귀 호출로 인해 스택 오버헤드가 발생할 수 있음.
📌 재귀적 방식(메모이제이션 없이)과의 비교
public static long fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2); // 중복 계산 발생
}- 중복되는 계산이 많아 성능이 매우 떨어짐.
- 예를 들어
fib(5)를 계산할 때fib(3)을 두 번 계산하는 등 중복이 심함.
2. Bottom-Up (Tabulation)
작은 문제부터 해결해 나가면서, 그 결과를 저장하여 큰 문제를 해결하는 방식
long[] dp = new long[n + 1]; // n번째 피보나치 수를 저장할 배열
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 차례로 값을 구함
}- 작은 문제부터 해결해나가며 모든 값을 구함.
- 재귀호출 없이 반복문을 사용하므로 재귀 호출이 없어 스택 오버헤드가 발생하지 않음.
💻 피보나치 수[BOJ 2748] 전체 코드
1. Top-Down 방식 (메모이제이션) 전체 코드
import java.util.Scanner;
public class FibonacciTopDown {
static long[] memo;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
memo = new long[n + 1]; // 메모이제이션을 위한 배열
System.out.println(fib(n));
}
public static long fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (memo[n] != 0) return memo[n]; // 이미 계산한 값은 재사용
memo[n] = fib(n - 1) + fib(n - 2); // 재귀 호출
return memo[n];
}
}2. Bottom-Up 방식 (탭 구조)
import java.util.Scanner;
public class FibonacciBottomUp {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if (n == 0) {
System.out.println(0);
return;
}
long[] dp = new long[n + 1]; // n번째 피보나치 수를 저장할 배열
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 차례로 값을 구함
}
System.out.println(dp[n]);
}
}