다이나믹 프로그래밍이란
개요
- 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법
- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
- 완전탐색과 같이 비효율적인 시간복잡도를 가지는 문제라고 하더라도 다이나믹 프로그래밍으로 시간복잡도를 획기적으로 줄일 수 있다.
- 다이나믹 프로그래밍의 구현은 일반적으로 두가지 방식(탑다운, 보텀업)으로 구성됨
- 동적 계획법이라고도 부른다.
✅참고 : 일반적인 프로그래밍 분야에서의 동적(Dynamic)의 의미
- 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미
- 반면 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다.
사용 조건
1. 최적 부분 구조
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결 할 수 있다.
2. 중복되는 부분 문제
동일한 작은 문제를 반복적으로 해결해야 한다.
예제 : 피보나치 수열
피보나치 수열은 다음과 같다.
1 1 2 3 5 8 13 21 34 55 89 ...
✅ 점화식
인접한 항들 사이의 관계식을 의미
✅ 피보나치 수열의 점화식 표현
재귀함수를 이용해 점화식 형태 그대로 구현 가능
비효율적으로 구현
public class Main {
// 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
public static int fibo(int x) {
if (x == 1 || x == 2) {
return 1;
}
return fibo(x - 1) + fibo(x - 2);
}
public static void main(String[] args) {
System.out.println(fibo(4));
}
}문제점
- 단순 재귀함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 된다. (비효율적)
✅ 참고 : 피보나치 재귀함수의 지수 시간 복잡도
O(2^트리높이N) - 다음과 같이 f(2)가 여러번 호출된다. (중복되는 부분 문제)
다이나믹 프로그래밍으로 구현
피보나치 수열은 다이나믹 프로그래밍의 사용 조건을 만족하므로 다이나믹 프로그래밍으로 효과적으로 계산할 수 있다.
✅ 피보나치 수열의 다이나믹 프로그래밍 사용 조건 충족
1. 최적 부분 구조
큰 문제(ex. f(4))를 작은문제(ex. f(3)+f(2))로 나눌 수 있다.
2. 중복되는 부분문제
동일한 작은 문제를 반복적으로 해결 (ex. f(2)의 중복)
탑다운
- 구현 과정에서 재귀함수 사용
큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출
(작은 문제가 모두 해결 되었을 때 큰 문제에 대한 답을 얻을 수 있다) - 재귀호출 과정에서 메모이제이션(DP) 이용하여 중복되는 부분 문제 해결
✅ 메모이제이션
- 한번 계산한 (작은문제에 대한) 결과를 메모리 공간에 메모하는 기법
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
- 엄밀히 말하면 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념이므로 다이나믹 프로그래밍에 국한된 개념은 아니다.
- 동작분석
a.단순 재귀함수와 비교
b. 실제 호출
- 파란색 : 호출 + 연산 및 값 저장
- 실선 : 호출 + 바로 return
=> 파란f(3)에서 앞서 값 저장되었기 때문에 실선f(3)은 호출되었지만 바로 return되고 따라서 더 깊게 들어가지 않는다.
=> 상수시간(return)을 무시하여 O(N)
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은 아래에서 위로 올라가면서, 이미 그 자체만으로도 반복되는 부분문제들에 대한 메모이제이션을 진행하며 풀어나가게 된다.(참고) - 반복문 과정에서 결과 저장용 리스트(DP) 이용
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]);
}
}다이나믹 프로그래밍 VS 분할 정복
- 다이나믹 프로그래밍과 분할 정복(ex. 퀵정렬)은 모두 최적 부분 구조를 가질 때 사용 가능
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황 - 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복 여부
- 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복
- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산 되지 않음
다이나믹 프로그래밍 문제에 접근하는 방법
- 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요
- 문제가 주어졌을 때, 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결 할 수 있는지 검토할수있다.
- 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려하자 - 재귀함수로 비효율적인 완전탐색 프로그램을 작성 한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용 될 수 있으면 메모이제이션 사용으로 코드를 개선
- 일반적인 코테 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제
