[알고리즘 정리] 다이나믹 프로그래밍

DP?

여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

int fibo(int n){
	if(n <= 1) return 1;
    return fibo(n-1) + fibo(n-2);
}

피보나치 수열의 N번재 항을 지금처럼 재귀적으로 구하면 중복된 연산이 계속 발생해서 O(1.618^N)의 시간이 걸린다.

int fibo(int n){
	int f[20];
    f[0] = f[1] = 1;
    for(int i = 2; i <= n; i++)
    	f[i] = f[i-1] + f[i-2];
	return f[n];
}

DP로 해결하면 미리 배열을 만들어두고 0번째 인덱스부터 하나씩 채워가는 방식으로 해결할 수 있다.
이렇게 중간 결과를 저장해서 이용하는지 그렇지 않은지에 따라 극적인 시간복잡도의 차이가 발생한다.

DP를 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

1로 만들기

연습 문제

1. 테이블 정의하기
   D[i] = i 를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값

2. 점화식 찾기

D[12] = ?
3으로 나누거나 D[12] = D[4] + 1
2로 나누거나 D[12] = D[6] + 1
1을 빼거나 D[12] = D[11] + 1
-> D[12] = min(D[4] + 1, D[6] + 1, D[11] + 1)

D[k] = ?
3으로 나눠지면 3으로 나누거나 D[k] = D[k/3] + 1
2로 나눠지면 2로 나누거나 D[k] = D[k/2] + 1
1을 빼거나 D[k] = D[k-1] + 1 이들 중에서 최솟값

3. 초기값 정의하기
   D[1] = 0

연습 문제 2

1, 2, 3 더하기

연습 문제 3

계단 오르기

연습 문제 4

RGB 거리

연습 문제 5

2xn 타일링