다이나믹 프로그래밍(DP)
- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
- 이미 계산된 결과(작은 문제)는 별도의 메로리 영역에 저장
- Top-down
- Bottom-up
다음 조건을 만족할 때 사용가능
- 최적 부분 구조
- 큰문제를작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
- 중복되는 부분 문제
- 동일한 작은 문제를 반복적으로 해결해야 한다.
예) 피보나치 수열
Top-down으로 구현한 피보나치 (재귀)
import java.util.*;
public class Main {
// 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화
public static long[] d = new long[100];
// 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
public static long fibo(int x) {
// 종료 조건(1 혹은 2일 때 1을 반환)
if (x == 1 || x == 2) {
return 1;
}
// 이미 계산한 적 있는 문제라면 그대로 반환
if (d[x] != 0) {
return d[x];
}
// 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
public static void main(String[] args) {
System.out.println(fibo(50));
}
}
Bottom-up
import java.util.*;
public class Main {
public static long[] d = new long[100];
public static void main(String[] args) {
// 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1;
d[2] = 1;
int n = 50; // 50번째 피보나치 수를 계산
// 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for (int i = 3; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
System.out.println(d[n]);
}
}
'코딩테스트 > [알고리즘] 알고리즘 정리' 카테고리의 다른 글
문자열 패턴 매칭 알고리즘 (0) | 2022.02.24 |
---|---|
이진 탐색 알고리즘 (0) | 2021.10.07 |
그리디 알고리즘 (0) | 2021.10.04 |
백트래킹 알고리즘 (0) | 2021.10.03 |
그래프 탐색 알고리즘 - DFS / BFS (0) | 2021.10.02 |