동적 계획법
동적 계획법(dynamic programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
부분 문제 반복과 최적 부분 구조를 가지는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
1. 동적 계획법의 조건
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);
}
만약 fibo(7)을 구하는 과정을 도식화 해보면 아래 이진 트리와 같다.
7번째 값을 구하기 위해 25번의 함수 호출이 진행된다.
이 과정에서 fib(5) ,fib(4), fib(3)들이 이미 진행했던 연산임에도 재귀되며 반복적으로 연산 하는 것을 볼 수 있다.
이러한 반복적인 연산을 부분 반복 문제(Overlapping Subproblem)이라고 한다.
어떤 문제가 여러 개의 부분 문제(Subproblem)으로 쪼개질 수 있을 때 사용하는 용어이다.
모든 문제를 부분 문제로 쪼갤 수 있고, 재귀 함수를 통해 해결 할 수 있다.
2) 최적 부분 구조(Optimal Substructure)
최적 부분 구조 : 작은 부분 문제에서 구한 최적의 답으로 합쳐진큰 문제의 최적의 답을 구할 수 있어야 한다.
예를 들면,
fib(n) = fib(n-1) + fib(n-2);
fib(n)이 최적의 답이 되려면 작은 부분 문제인 fib(n-1)과 fib(n-2)이 최적의 답이어야 한다.
작은 부분 문제의 최적의 답으로 큰 문제의 최적의 답을 구할 수 있는 것이다.
최적 부분 구조를 만족한다면, 문제에 크기에 상관없이 어떠한 문제의 답은 일정하다.
예를 들면,
fib(7)에서 구한 fib(4)
fib(6)에서 구한 fib(4)
fib(5)에서 구한 fib(4)
fib(4)에서 구한 fib(4)
에서 fib(4)의 값들이 항상 같은 값인 것이다.
그러므로 fib(4)를 반복해서 연산하는 것은 의미가 없다.
(이 반복되는 연산 과정을 줄이기 위해서는 어떻게 해야 할까?)
2. 메모이제이션(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)라고 부른다.
3. 동적 계획법 접근 방법
1) 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];
}
위 방식처럼 재귀 호출을 통해 피보나치 수 구하는 방식에 해당한다.
2) Bottom-Up
아래에서 위로 접근하는 방법이다.
부분 문제에서부터 문제를 풀어가며 점차 큰 문제를 풀어가는 방법이다.
// 최대 범위 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];
}
위 방식처럼 for문에서 배열을 이용하여 푸는 방법에 해당한다.
4. 동적 계획법 활용 방법
실제 코딩테스트에서 DP에 해당하는 문제 풀이에 활용할 때는 다음 방법과 같다.
- 문제에서 요구하는 답을 문장으로 표현한다.
- 문장에 나와있는 변수 개수 만큼 메모를 위한 캐시 배열을 생성한다.
- 문제를 부분 문제로 나누고, 점화식을 구하여 문제를 함수로 표현한다.
- Top-Down의 경우 재귀 함수, Bottom-Up의 경우 for문을 활용하여 답을 도출한다.
이러한 동적 계획법은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식이다.
이와 대비되는 탐욕 알고리즘(그리드 알고리즘)과 이점을 잘 비교하여 문제에 적용해야 한다.
🧐 모든 해를 구하지 않고 순간마다 그 순간에서의 최적의 해를 찾는 알고리즘
동적 계획법 : 항상 최적의 해를 검출하지만 시간이 오래 걸린다.
탐욕 알고리즘 : 최적의 해가 아닐 수 있지만 시간이 짧게 걸리는 장, 단점들을 서로 비교해야 한다.
참고자료
'알고리즘 > 알고리즘 종류 설명' 카테고리의 다른 글
| 완전 탐색이란 무엇인가? (0) | 2021.08.18 |
|---|---|
| Dijkstra 알고리즘이란 무엇인가? (0) | 2021.08.15 |
| Floyd 알고리즘이란 무엇인가? (0) | 2021.08.14 |
| Backtracking이란 무엇인가? (0) | 2021.08.04 |
| DFS, BFS란 무엇인가? (0) | 2021.07.29 |
댓글