동적 계획법 (DP, Dynamic Programming)
동적 계획법(DP, Dynamic Programming)
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
부분 문제 반복과 최적 부분 구조를 가지는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
DP를 사용하는 이유(조건 정리)
우선 DP를 배우고자 하는 사람들은 DP 문제를 접하고 나서 온 것일것이다. 그럼 가장 기초적인 궁금증 도데체 왜 DP를 사용하는 것일까?
만약 우리가 문제를 푸는 과정에서 재귀 함수를 사용하는 경우가 분명히 존재한다. 재귀의 경우 같은 로직을 여러번 반복하기 때문에 굉장히 비효율적인 계산을 하게 된다
가장 대표적인 재귀문제 피보나치 수열을 예로 들어보자
int fibo(int n) {
if (n <= 2) return 1;
return fibo(n - 1) + fibo(n - 2);
}이런식으로 이전의 값과 현재의 값을 확인 할 수 있는데 우리가 주의 깊게 볼 것은 바로 반복된 계산이다.
만약 저 위에 식으로 n = 5를 넣었을때 이런식으로 계산하게 되는데 fibo(3)을 보면 계산식이 반복된다는 것을 알 수 있다.
이때! DP를 사용하는 것이다 진행하는 계산이 이미 진행한 적이 있던 계산이라면 그 값을 불러오는 것이다
동적 계획법의 조건 정리
1. 부분 반복 문제
위에서 잠깐 예시로 들었던 이미 진행한 연산을 반복하게 되면서 나타나는 현상이 부분 반복 문제이다.
- 어떤 문제가 여러 개의 부분 문제로 쪼개질 수 있을때 사용하는 용어
- 모든 문제를 부분 문제로 쪼갤 수 있고, 재귀 함수를 통해 해결 할 수 있다.
2. 최적 부분 구조
작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다.
이또한 비슷한 말이다. 예를 들자면
fibo(8)를 위해 연산해야하는 fibo(4)
fibo(7)를 위해 연산해야하는 fibo(4)
fibo(6)를 위해 연산해야하는 fibo(4)
fibo(5)를 위해 연산해야하는 fibo(4)
fibo(4)를 위해 연산해야하는 fibo(4)
보다시피 fibo(4)는 어차피 같은 값이다. 즉, 최적 부분 구조를 만족한다면, 문제에 크기에 상관없이 어떠한 문제의 답이 일정하다
메모이제이션
연산 과정을 줄이기 위해 메모이제이션이라는 동적 프로그래밍의 개념이 도입되게 되었다.
메모이제이션은 컴퓨터 프로그램이 동일한 계산을 반복해야 할때, 이전의 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이다
int memo[101];
memo[1] = 1;
memo[2] = 1;
int fibo(int n) {
if(memo[n] != 0) {
return memo[n];
}
memo[n] = fibo(n - 1) + fibo(n - 2);
return memo[n];
}위에 보이는 것처럼 구하고자 하는 숫자의 크기만큼 배열을 생성하고 계산한 값을 저장하고 저장된 값일 경우(초기값 0이 아닌 경우) 배열의 값을 리턴하는 방식으로 구현하면 중복되던 연산 과정을 줄일 수 있게 된다.
저장해 두는 메모리(배열)을 캐시(Cache)라고 부른다
동적 계획법 접근 방법
Top - Down 방식
높은 곳(큰 값)에서 낮은 곳(작은 값)으로 향해 가며 답을 구하는 것이다.
가장 좋은 예로 재귀 함수를 볼 수 있다.
int memo[101];
memo[1] = 1;
memo[2] = 1;
int fibo(int n) {
if(memo[n] != 0) {
return memo[n];
}
memo[n] = fibo(n - 1) + fibo(n - 2);
return memo[n];
}이처럼 재귀적 호출을 통해 피보나치 수를 구하는 방식에 해당한다
Bottom - Up 방식
낮은 곳(작은 값)에서 높은 곳(큰 값)으로 향해 가며 답을 구하는 것이다.
int memo[101];
memo[1] = 1;
memo[2] = 1;
int fibo(int n) {
for(int i = 0; i <= n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n];
}이처럼 for문을 통해 배열을 이용해서 푸는 방식이 있다.
동적 계획법 활용 방법
- 문제에서 요구하는 답을 문장으로 표현한다.
- 문장에 나와있는 변수 갯수 만큼 메모를 위한 캐시 배열을 생성한다
- 문제를 부분 문제로 나누고, 점화식을 구하여 문제를 함수로 표현한다
- Top - Down의 경우 재귀함수, Bottom - Up의 경우 for문을 활용해서 답을 도출한다.
이러한 동적 계획법은 모든 방법을 일일이 검토하여 최적의 답을 찾아낸다.
이와 대비되는 그리디알고리즘과 이점을 잘 비교해서 문제에 적용해야한다.
- DP(동적 계획법) : 항상 최적의 답을 검출하지만 시간이 오래 걸린다
- Greedy(탐욕 알고리즘) : 최적의 답은 아닐수 있지만 시간이 짧게 걸리는 장, 단점을 서로 비교