DP(동적계획법)

메모이제이션(memoization)

- 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술

- 추가적인 메모리 공간이 필요하다

- 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우가 발생할 수 있다

 

재귀

if(n<N) return n;
return DP(n-1)+DP(n-2);

 

메모이제이션을 사용한 재귀

if(n>=N && memo[n]==0) memo[n] = DP(n-1)+DP(n-2);
return memo[n];

 

동적계획법(Dynamic Programming)

그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘

먼저 작은 부분 문제들의 해들을 구하고 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로는 원래 주어진 문제를 해결하는 알고리즘 설계 기법

재귀(하향식) n항을 구하기 위한 n-1과 n-2... 항들을 구한다

DP(상향식) n항을 구하기 전 1, 2, ... n-2, n-1 항들을 구한다

 

- 다음과 같은 요건을 가지고 있어야 한다

1) 최적 부분문제 구조(Optimal substructure)

2) 중복 부분문제 구조(Overlapping subproblems)

 

최적 부분문제 구조(Optimal substructure)

- 최적화의 원칙(Principle of Optimality) : 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다

- 만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법을 사용할 수 없다

- 최적의 원칙이 적용되지 않는 예: 최장경로(Longest Path) 문제

 

중복 부분문제 구조(Overlapping subproblems)

- DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해(Optical Solution)를 이용하여 순환적으로 큰 문제를 해결한다

>> 순환적인 관계(recurrence relation)를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적 도구인 점화식(어떤 수열의 각각의 항들의 관계를 나타낸 식)을 사용한다

- DP는 문제의 순환적인 성질 때문에 이전에 계산되었던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데(Overlapping subproblems) 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간(table)에 저장하게 된다

- 저장된 해들이 다시 필요할 때마다 해를 얻기 위해 다시 문제를 재계산하지 않고 table의 참조를 통해서 중복된 계산을 피하게 된다

 

분할 정복과의 차이

분할 정복	DP
- 연관 없는 부분 문제로 분할 - 부분문제를 재귀적으로 해결 - 부분문제의 해를 결합(combine)한다 - 예: 병합 정렬(결합), 퀵 정렬(결합 x) - 하향식 방법으로 접근	- 부분 문제들이 연관이 없으면 적용할 수 없다 - 부분 문제들 사이에 의존적 관계 존재 - 관계가 문제에 따라 다르고, 대부분의 경우 뚜렷하게 보이지 않아서 함축적인 순서(implicit order)라고 한다 - 모든 부분 문제를 한 번만 계산하고 결과를 저장하고 재사용한다 - 상향식 방법으로 접근

 

DP 적용 접근 방법

1) 최적해 구조의 특성을 파악하라

 - 문제를 부분 문제로 나눈다

2) 최적해의 값을 재귀적으로 정의하라

 - 부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의한다

 - 점화식으로 정의

3) 상향식 방법으로 최적해의 값을 계산하라

 - 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다

 - 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다(상향식 방법)

 

DP 적용 알고리즘

for(int i = 0; i<N; i++) {
     DP[i] = DP[i-1] + DP[i-2];
}

 

최단 경로(shorest Path)

- 한 도시에서 다른 도시로 가장 빨리 갈 수 있는 경로를 찾는 문제

- 가중치 포함, 방향성 그래프에서 최단 경로 찾기

>> 가중치가 없는 그래프의 최단(bfs)

>> 양수만 있을 때(다익스트라)

>> 음수의 가중치가 있거나, 모든 쌍의 최단을 구할 때(플로이드-워샬)

- 최적화 문제(optimization problem)

>> 주어진 문제에 대해서 하나 이상의 많은 해답이 존재할 때, 이 가운데에서 가장 최적인 해답(optimal solution)을 찾아야 하는 문제

 

DP 접근 방법

- 각 정점을 시작 정점으로 정하여 다익스트라(Dijkstra)의 최단 경로 알고리즘을 수행

- 정점 1에서 정점 k까지의 모든 정점들을 반드시 경유하는 경로를 의미하는 것이 아니다

1) 부분 문제를 찾는다 -> 정점의 개수를 줄여 본다

2) 부분 문제 정의: 정점만을 경유 가능한 정점들로 고려하여, 정점 i로부터 정점 j까지의 모든 경로 중에서 가장 짧은 경로의 거리

3) 경유 가능한 정점들을 하나씩 늘린다

// 경찰과 도둑으로 암기
for(int k = 1; k<=N; k++) { // 경유지
	for(int i = 1; i<=N; i++) { // 출발지
		for(int j = 1; j<=N; j++) { // 도착지
        		// 경유지를 거쳐서 오는 비용과, 직전 최적해 중 가장 작은 해를 유지
        		DP[i][j] = Math.min(DP[i][k] + DP[k][j], DP[i][j]);
		}
	}
}