Dynamic Progamming 이란?
- 알고리즘에서의 '동적'은 별 의미가 없다. '기억하기'로 생각하면 편하다.
- '프로그래밍'은 '테이블을 만든다'는 뜻이라고 생각하면 됨.
중복되는 문제
- 피보나치 수열 코딩 시, F(n) = F(n-1) + F(n-2) 이기 때문에 단순 재귀 함수로 구현하면..
public class Simple {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp = new int[n+1];
System.out.println(fibo(n));
}
// 단순 재귀
static int fibo(int x) {
if( x ==1 || x==2) return 1;
return fibo(x-1) + fibo(x-2);
}
}- 위 코드와 같이 메모이제이션을 사용하지 않으면, 같은 함수를 중복 호출하기 때문에
재귀 함수로 구현하면 시간 복잡도 O(2^N)을 갖는다. - 중복되는 호출로 인해 굉장히 좋지 않은 효율을 갖는다.
DP 문제가 성립할 조건
- 최적 부분 구조 (Optimal Substructure) : 상위 문제를 하위 문제로 나눌 수 있으며 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다! ( 겨수님 : "작은 문제의 답들 사이의 관계.. ")
- 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다.
피보나치 수열은 DP 사용 조건에 만족한다.
DP 알고리즘 기법은 무엇인가?
- DP 알고리즘 기법은 이미 계산된 (하위 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 설계함으로써,
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. - DP 구현 방법은 일반적으로 두 가지 방식, Top-down(하향식)과 Bottom-up(상향식)으로 구성된다.
Top-down (하향식)
- 상위 문제를 해결하기 위해서 하위 문제를 재귀적으로 호출하여 상위 문제를 해결하는 방식
하위 문제를 저장해 놓기 위해 Memoization이 사용된다. - 하향식 방식은 재귀 호출을 사용하여 구현한다.
public class Topdown {
static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp = new int[n+1];
System.out.println(fibo(n));
}
static int fibo(int x) {
if(x == 1 || x == 2) {
return 1;
}
if(dp[x] != 0) {
return dp[x];
}
dp[x] = fibo(x-1) + fibo(x-2);
return dp[x];
}
}Bottom-up (상향식)
- 하위에서부터 문제를 해결해나가면서 먼저 계산했던 문제들의 값을 활용해서 상위 문제를 해결해나가는 방식
- DP의 전형적인 형태인 상향식 방법이다.
- 여기서 사용되는 문제 결과 값 저장용 리스트는 DP 테이블이라고 부른다.
- 상향식은 반복문을 사용하여 구현한다.
public class BottodmUp {
static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp = new int[n+1];
System.out.println(fibo(n));
}
static int fibo(int x) {
dp[1] = 1;
dp[2] = 1;
for(int i=3; i<x+1; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[x];
}
}
Memoization
- 메모이제이션은 DP 구현 방법 중의 하나로, 한번 계산된 결과를 메모리 공간에 메모하는 기법이다.
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
- 값을 기록한다는 부분에서 캐싱이라고도 함.
- DP에만 국한된 개념이 아니다. 한 번 계산된 결과를 담아 놓기만 하고 DP 가 아닌 다른 방식으로 사용될 수 있다.
[알고리즘] 동적계획법 DP (Dynamic Programming) 정리 (Java)
동적계획법 Dynamic Programming 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로, 이름만 가지고는 무엇을 의미하는지 영 알 수 없기 때문에 가장 많은 오해를
loosie.tistory.com
'Algorithm' 카테고리의 다른 글
| 투포인터 (Two Pointers) (2) | 2024.01.18 |
|---|---|
| Char 형의 모든 것 (2) | 2024.01.18 |
| DFS (Depth-First Search) (1) | 2024.01.18 |
| 위상정렬(Topological Sort) (1) | 2024.01.10 |
