동적계획법 - 다이나믹 프로그래밍(DP)
- 문제를 잘게 쪼개서 부분문제를 중복되어 재활용됨, 피보나치 수열 활용
- 메모이제이션 기법 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법)
분할정복
- 하향식 접근법, 일반적으로 재귀함수 활용
- 문제를 잘게 쪼갤때 부분문제는 중복되지 않음 ex.병합정렬 또는 퀵정렬 활용
(공통점) 동적계획법과 분할정복
- 문제를 잘게 쪼개서, 가장 작은 단위로 분할
- (차이점) DP 동적계획법 : 부분문제 중복되어, 상위문제 해결시 재활용
동적 계획법 알고리즘 이해
- 피보나치 수열
def fibo(num):
if num <= 1:
return num
return fibo(num -1) + fibo(num -2)동적 계획법의 조건
동적 계획법을 적용하려면 위 정의에서 본 것 처럼 두 가지 속성을 만족 시켜야 하는데,
- 부분 반복 문제(Overlapping Subproblem)
- 최적 부분 구조(Optimal Substructure)
위 두 가지 속성을 만족 시켜야 한다.
1. 부분 반복 문제(Overlapping Subproblem)
동적 계획법의 등장은 피보나치 수열에서 시작되었다고 하는데,
피보나치 수열은 대표적인 재귀 함수로 아래와 같이 표현 할 수 있다.
fib(1) = 1; fib(2) = 1;
fib(n) = fib(n-1) + fib(n-2);
// 메소드로 표현한 피보나치 수열
int fib(int n)
{
if (n <= 2)
return 1;
else
return fib(n-1) + fib(n-2);
}2. 최적 부분 구조(Optimal Substructure)
최적 부분 구조란, 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것이다.
아래 피보나치 수열의 식에서
fib(n) = fib(n-1) + fib(n-2);큰 문제의 답인 fib(n)이 최적의 답이 되려면 작은 부분 문제인 fib(n-1)과 fib(n-2)이 최적의 답이어야 한다.
작은 부분 문제의 최적의 답으로 큰 문제의 최적의 답을 구할 수 있는 것이다.
fib(n-1)을 구하기 위해서 다시 fib(n-2) + fib(n-3)이 되고, 이 때 fib(n-2)가 중복이 된다.
그리고 최적 부분 구조를 만족한다면, 문제에 크기에 상관없이 어떤 한 문제의 답은 일정하다.
예를 들어 설명 해보면
fib(7)에서 구한 fib(4)
fib(6)에서 구한 fib(4)
fib(5)에서 구한 fib(4)
fib(4)에서 구한 fib(4)
이 fib(4)의 값들이 항상 같은 값인 것이다.
그렇다면 fib(4)를 반복해서 연산하는 것은 의미가 없다.
3. 메모이제이션(Memoization)
이를 해결하기 위해서 메모이제이션(Memoization) 이라는 동적 프로그래밍의 개념이 도입되게 되는데
메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
다시 말해 메모리에 계산한 값을 저장해 나감으로써
다음 반복 수행때는 연산 없이 저장된 값을 불러와 주는 방법이다.
앞서 살펴본 피보나치 수열의 재귀 함수를 메모이제이션을 적용하면 아래와 같다.
// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];
memo[1] = 1;
memo[2] = 1;
// 메소드로 표현한 피보나치 수열
int fib(int n)
{
if (memo[n] != 0)
return memo[n];
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}위 처럼 구하고자 하는 숫자의 크기 만큼 배열을 생성하고 계산한 값을 저장하고
저장된 값일 경우(초기값 0이 아닌 경우) 배열의 값을 리턴하는 방식으로 구현하면
중복되던 연산 과정을 줄일 수 있게 된다.
✋이때 저장해 두는 메모리(배열)을 캐시(Cache)라고 부른다.
4.1 Top-Down
Top-Down 방법은 말 그대로 위에서 아래로 접근하는 방법으로
큰 문제에서 부분 문제로 쪼개가며, 재귀 호출을 이용하여 푸는 방법이다.
아래 방식처럼 재귀 호출을 통해 피보나치 수를 구하는 방식에 해당한다.
// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];
memo[1] = 1;
memo[2] = 1;
// 메소드로 표현한 피보나치 수열
int fib(int n)
{
if (memo[n] != 0)
return memo[n];
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}4.2 Bottom-Up
Bottom-Up 방법은 말 그대로 아래에서 위로 접근하는 방법으로
부분 문제에서 부터 문제를 풀어가며 점차 큰 문제를 풀어가는 방법이다.
for문을 이용하여 푸는 방법에 해당한다.
// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];
memo[1] = 1;
memo[2] = 1;
// 메소드로 표현한 피보나치 수열
int fib(int n)
{
for(int i = 3; i <=n; i++){
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
}