동적계획법(Dynamic Programming) 알고리즘
- 복잡한 문제를 풀기 위해 작은 하위 문제로 나누고, 이전 계산 결과를 저장하여 반복 계산을 줄이는 방법
- 피보나치, DFS, BFS, 완전 탐색 등의 알고리즘으로는 반복되는 작업이 많을 때 최적화를 노리는 알고리즘
동작 원리
- 문제를 최정 부분 구조로 나누고, 중복되는 하위 문제를 해결.
- 문제를 재귀적으로 풀 때 같은 문제를 여러번 계산하지 않고 한 번 계산한 결과를 저장해 다시 사용
장점
- 하위 문제들의 결과를 저장해 반복을 줄임
- 최적화, 그래프탐색 등 중복되는 연산이 있는 다양한 분야에 적용 가능
단점
- 추가적 메모리가 필요할 수 있어 공간복잡도에서 불리할 수 있음
- 중복 부분 문제를 만족하지 않는 문제에는 적용이 어려움
활용 사례
1. 피보나치 수열 계산 : 이전 2개 항의 합을 저장하기에 중복 계산이 많음. 이를 미리 저장해두어 중복 계산을 피함
2. 최장 증가 부분 수열 : 두 문자열에서 공통으로 존재하는 부분 수열 중 가장 긴 것을 찾는 문제
3. 배낭 문제 : 제한된 무게 내에서 가장 큰 가치를 찾는 문제
4. 동전 거스름돈 문제 : 주어진 금액을 만들기 위해 필요한 최소의 동전 개수를 찾는 문제
코드 구현 (피보나치 수열)
DP를 이용한 코드
>> 이전 항의 값을 별도 배열에 저장!
public class FibonacciDP {
// 피보나치 수열을 동적 계획법으로 계산하는 메서드
public static int fibonacci(int n) {
if (n <= 1) {
return n; // n이 0 또는 1이면 그 값을 반환
}
// 피보나치 수를 저장할 배열 선언
int[] fib = new int[n + 1];
fib[0] = 0; // F(0) 초기화
fib[1] = 1; // F(1) 초기화
// Bottom-Up 방식으로 피보나치 수열 계산
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n]; // n번째 피보나치 수 반환
}
public static void main(String[] args) {
int n = 10; // 예시로 n = 10
System.out.println("피보나치 수열의 " + n + "번째 값: " + fibonacci(n));
}
}
일반 코드
public class Fibonacci {
// 피보나치 수열을 동적 계획법으로 계산하는 메서드
public static int fibonacci(int n) {
if (n <= 0) {
return 0;
}
if (n <= 2) {
return 1;
}
return fibonacci(n-1) + fibonacci(n-2);
}
public static void main(String[] args) {
int n = 10; // 예시로 n = 10
System.out.println("피보나치 수열의 " + n + "번째 값: " + fibonacci(n));
}
}