특별한 속성을 가진 복잡한 문제를 푸는 방법
복잡한 문제를 단순한 하위 문제로 나눠서 푼다
특별한 속성이 있는 경우에만 가능하며 모든 문제가 가능하진 않다
메모이제이션(memoization)
계산 결과를 캐시에 저장해 둔 뒤 나중에 재사용하는 기법
처음 계산 시 결과를 캐시에 저장하고 나중에 같은 계산을 하는 경우 저장해둔 값을 사용
깊은 재귀 호출에 적합
최적화 기법 중 하나, 캐싱 기법 중 하나
보통 함수나 매개변수에 따라 변환하는 값을 캐싱하는 것을 지칭
메모이제이션을 사용한 피보나치 함수(top-down 동적 계획법)
public static int fibonacciRecursive(int number, int[] cache) {
//종료 조건
if (number <= 1) {
return number;
}
//앞 전에 계산하여 캐시에 등록된 조건이 있는 경우 값 바로 리턴
if (cache[number] != 0) {
return cache[number];
}
//한번도 계산한적 없는 경우 값을 캐시에 저장하고 값 리턴
int ret = fibonacciRecursive(number - 2, cache) + fibonacciRecursive(number - 1, cache);
cache[number] = ret;
return ret;
}타뷸레이션(tabulation)
가장 작은 문제(리프) 부터 시작
순서대로 그보다 하나 더 큰 문제를 풀어나감
ㄴ 필요하지 않은 하위 문제도 평가할 수 있음
ㄴ 문제를 잘 분석해서 최적의 순서를 찾아야 함
top-down 방식보다 보통 더 빠름
ㄴ CPU 캐시에 친화적
ㄴ 재귀 함수 호출을 피할 수 있음
ㄴ 모든 하위 문제를 평가할 필요가 없는 경우에는 예외
타뷸레이션을 사용한 피보나치 수열(bottom-up 동적 계획법)
public static int fibonacci(int nubmer) {
int cache[] = new int[number + 1];
//고정 값 0, 1
cache[0] = 0;
cache[1] = 1;
for (int i = 2; i < = number; ++i) {
cache[i] = cache[i - 2] + cache[i - 1];
}
}속도
메모이제이션/타뷸레이션은 속도 향상을 위한 기법
속도를 위해 메모리를 더 사용
시간 복잡도와 공간 복잡도가 반비례인 관계가 있음
동적 계획법을 적용할 수 있는 문제의 특징
최적 부분 구조(optimal substructure)
ㄴ 하위 문제의 최적 해법으로부터 큰 문제의 최적 해법을 구할 수 있음
ㄴ 동적 계획법과 그리디 알고리듬의 유용성 판단에 사용
ㄴ 강화 학습에서 흔히 등장하는 벨만 방정식도 이에 기초
하위 문제의 반복
ㄴ 똑같은 평가를 반복해야 하는 경우
ㄴ 하위 문제의 크기가 작은 경우
ㄴ 피보나치 수열 같은 케이스
동적 계획법으로 문제를 푸는 과정
문제에 동적 계획법을 사용할 수 있는지 판단
상태와 매개변수를 결정
상태 간의 관계를 정립
종료조건을 결정
메모이제이션 혹은 타뷸레이션을 추가
동적 계획법 적용 가능한 문제 판단
패턴
ㄴ 어떤 제약 하에 어떤 값을 최적화(최대/최소)
ㄴ 재귀 함수에 동일한 매개변수가 반복적으로 전달
그리드 작성
ㄴ cell 안의 값이 보통 최적화하려는 값
ㄴ 문제를 하위 문제로 어떻게 나눌지 생각할 것(각 cell 이 하위 문제)
ㄴ 위와 같이 하면 x/y 축 결정에 도움이 됨
동적 계획법으로 풀 수 있는 문제들
최단 경로 찾기(다익스트라 알고리듬)
최장 공통부분 문자열
와일드카드 패턴 매칭
부분집합 합
레벤슈타인 거리(편집 거리)
연속 행렬 곱셈
등...
배낭 문제
public class Item {
private int value;
private int space;
public Item(int value, int space) {
this.value = value;
this.space = space;
}
public int getValue() {
return value;
}
public int getSpace() {
return space;
}
}
public class Program {
private static int getMaxValue(int numSpace, Item[] items) {
int numItems = items.length;
int cache[][] = new int[numItems][numSpace + 1];
for (int s = 1; s <= numSpace; ++s) {
//물건을 넣기 위한 공간이 할당하려는 공간 보다 큰 경우 continue
if (items[0].getSpace() > s) {
continue;
}
//같거나 작으면 캐시에 [0][공간] = [물건]
cache[0][s] = items[0].getValue();
}
for (int i = 1; i < numItems; ++i) {
for (int s = 1; s <= numSpace; ++s) {
if (items[i].getSpace() > s) {
cache[i][s] = cache[i - 1][s];
continue;
}
int remainingSpace = s - items[i].getSpace(); //남는 공간
//남는 공간에 대한 그리드 기준 - 1 행의 최대값
//더 작은값이 나올 수 없음이 보장됨
int remainingMaxValue = cache[i - 1][remainingSpace];
//마지막 배낭 칸까지 반복하여 - 1 행과 현재 행의 두 값을 비교하여 최대값을 캐시에 저장
int choice1 = cache[i - 1][s];
int choice2 = items[i].getValue() + remainingMaxValue;
cache[i][s] = Math.max(choice1, choice2);
}
}
return cache[numItems - 1][numSpace];
}
public static void main(String args[]) {
Item[] items = new Item[5];
items[0] = new Item(3, 5);
items[1] = new Item(9, 12);
items[2] = new Item(1, 2);
items[3] = new Item(5, 4);
items[4] = new Item(7, 9);
int maxValue = getMaxValue(15, items);
System.out.println(String.format("Max Value: %d", maxValue));
}
}