동적 계획법이란?
문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다.
하위 문제의 해결책이 다른 하위 문제의 해결책과 같은 경우 유용하다.
탐욕 알고리즘과의 비교
탐욕 알고리즘은 문제가 발생하면 그 상황에서의 최적의 해를 선택하는 방식의 알고리즘을 말한다. 순간적으로 볼 때는 최적의 해를 반환하지만 전체적으로 보았을 때 그렇지만은 않은 상황이 존재한다.
예를 들어, 길을 찾는 문제가 주어졌다면 출발지부터 목적지까지 가는 중, 갈림길과 마주했을 때 그 순간 가장 짧은 길로 가는 것이다. 하지만 동적 계획법은 모든 갈림길을 살펴본 후 최적의 길을 탐색하게 된다.
동적 계획법은 모든 경우의 수를 살펴봐야 하기 때문에 시작시 조금의 시간이 걸릴 수 있다는 단점이 있다.
동적 계획법 예제
동전 교환 문제
여러 동전 값 coins = [c1, c2, ... , ck] 이 주어지고 만들어야 하는 목표 액수 n이 주어진다.
coins를 이용하여 목표 액수 n을 만들 때, 가장 작은 수의 coins를 구하여라.
(coins를 중복하여 사용하여도 괜찮다.)
예) coins = [1, 3, 4] 이고 n = 6이다.
동적 계획법으로 최적해를 구한다면 최적해는 3+3 = 6으로 2개이다.
하지만, 탐욕 알고리즘을 적용하여 최적해를 구한다면 4+1+1 =6으로 3개가 된다.
따라서, 탐욕 알고리즘이 항상 최적해를 구하지는 못한다는 것을 알 수 있다.
위 문제를 코드로 작성해 보자면 다음과 같다.
public class Coins {
public static void main(String[] args) {
//코인
int coins[] = {1, 3, 4};
// 최적해 저장
int solution[] = new int[50];
//0은 0개의 coin으로 나타낼 수 있음
solution[0] = 0;
//50개의 최적해를 구한다
for(int x =1; x <= 49; x++) {
//무한대로 설정
solution[x] = (int) Double.POSITIVE_INFINITY;
for(int c: coins) {
//k번째 코인을 사용할 수 있을 경우
if( x-c >= 0 ) {
//코인을 사용한 경우+1과 사용하지 않은 경우 중 작은 경우를 저장
solution[x] = Math.min(solution[x], solution[x-c]+1);
}
}
}
//출력
for(int i = 0; i<50 ; i++) {
System.out.println("최적해" + i + ": " + solution[i] );
}
}
}
0은 0개의 coin으로 만들 수 있다. ( 이 조건은 기저 조건이다. )
최적해를 저장할 solution []을 만든다.
1. solution [x]를 무한대로 설정한다.
2. 각 코인들을 사용할 수 있는 경우, 사용했을 때와 사용하지 않았을 때 중 작은 값을 solution [x]에 저장한다.
3. 각 코인들을 사용하는 모든 경우의 수를 계산하고 과정을 반복한다.
