DP 알고리즘(동적 계획법)은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구현하는 방법을 뜻합니다.
원리와 구현 방식
- 큰 문제를 작은 문제로 나눌 수 있어야 한다.
- 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
모든 작은 문제들을 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이플을 이용한다. 이를 메모리제이션 기법이라고 한다. - 동적 계획법에는 톱-다운 방식과 바텀-업 방식이 있다.
ex) 피보나치 수열 공식
D[N] = D[N-1] + D[N-2] // N번째 수열 = N-1번째 수열 + N-2번째 수열
톱-다운 구현 방식
위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀 함수 형태로 구현한다.
import java.util.Scanner;
public class DP_TopDown {
static int[] D;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
D = new int[n + 1];
for (int i = 0; i <= n; i++) {
D[i] = -1;
}
D[0] = 0;
D[1] = 1;
fibo(n);
System.out.println(D[n]);
}
static int fibo(int n) {
if (D[n] != -1) // 기존에 계산한 적이 있는 부분의 문제는 재계산 하지 않고 리턴
return D[n];
return D[n] = fibo(n - 2) + fibo(n - 1);
// 메모리제이션: 구한 값을 바로 리턴하지 않고 DP 테이블에 저장한 후 리턴
}
}바텀-업 구현 방식
가장 작은 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식입니다. 주로 반복문의 형태로 구현합니다.
public class DP_BottomUp {
static int[] D;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
D = new int[n + 1];
for (int i = 0; i <= n; i++) {
D[i] = -1;
}
D[0] = 0;
D[1] = 1;
for (int i = 2; i <= n; i++) {
D[i] = D[i - 1] + D[i - 2];
}
System.out.println(D[n]);
}
}두 방식 중 좀 더 안전한 방식은 바텀-업 입니다. 톱-다운 방식은 재귀함수의 형태로 구현돼 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있지만, 실제 코딩 테스트에서 시 부분까지 고려하는 난이도는 잘 나오지 않습니다. 자신에게 좀 더 편한 방식을 선택해 사용하도록 합니다.
관련 문제
골드 이상의 문제는 난이도를 표기하였습니다.
私はゲームと日本が好きなBackend Developer志望生のOguです🐤🐤