Dynamic Programming

탐색과정에서 중복된 과정을 생략하는 알고리즘 작성 기법
그리디 알고리즘과 같이 최적화 문제를 해결하는 방법이다.

개념

• 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어서 문제를 효율적으로 해결하는 알고리즘 기법
• 어떤문제는 메모리공간을 약간 더 사용하면, 연산 속도를 비약적으로 증가 시킬 수 있다.
• 먼저 작은 문제의 부분의 해들을 구하고, 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 문제를 해결하는 알고리즘 기법이다.

다이나믹 프로그래밍을 사용하는 경우

• 큰 문제를 작은 문제로 나눌 수 있을 때
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때.
• 결과를 어떤 수로 나눈 것을 출력하라는 경우의 문제

조건

• 같은 인풋 -> 같은 결과
• A를 최대로 하싶은데 B에 대한 제한이 있다.
• 부분 문제들 사이에 의존적 관계가 존재한다.

---

DP 구현 방법 3가지

탑 다운(하향식)

• 재귀함수를 이용해서 다이나믹 프로그래밍 소스코드를 작성하는 방법
• 큰 문제를 해결하기 위해, 작은 문제를 호출하는 방법
• 가장 큰 문제를 방문 후, 문제를 호출하여 답을 찾는 방식

바텀 업(상향식)

• 단순한 반복문을 이용해서 소스코드를 작성하는 경우
• 작은 문제들을 답 부터 구하며 전체 문제의 답을 찾는 방식

메모이제이션

• 일반적인 DP문제 풀이 방법이다.
• 한번 구현한 결과를, 메모리공간에 메모해두고, 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 말한다.
• 다시 말해, 이전에 계산한 값을 동적으로 저장해서 중복된 계산을 안하는 것.
• 캐싱(Cashing) 이라고도 한다.

최적 부분 문제 구조

• 동적 계획 법이 최적화에 대한 어느 문제에 적용될 수 있는 것은 아니다.
• 주어진 문제가 최적화의 원칙을 만족해야하만 동적 계획법을 효율적으로 적용할 수 있다.

최적화의 원칙

어떤 문제에 대한 해가 최적일 때, 그해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다. 동적 계획법자체가 큰 문제의 최적 해 들을 이용하여 구하기 때문에 만약 큰 문제의 해가 작은 문제의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법을 적용할 수 없다.

중복 부분 문제 구조

• DP는 큰문제르 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰문제를 해결한다.
  • 순환적인 관계를 명시적으로 표현하기 위해서 동적 계획법에서는 수학적 도구인점화식을 이용한다.
• 이미 해결된 작은 문제들의 해들을 어떠한 저장공간에 저장하게된다.
• 그리고 저장된 해들이 다시 필요할 때마다 해를 얻기 위해서 다시 문제를 계산하지 않고 table의 참조를 통해서 중복된 계산을 피하게 된다.

분할정복과 동적 계획법의 비교

분할 정복

• 연관이 없는 문제로 분할한다.
• 재귀적으로 해결한다.
• 부분의 문제의 해를 결합한다.
• 하향식 방법으로 접근

DP

• 부분 문제들이 연관이 없으면 적용할 수 없다. 부분 문제들은 더 작은 부분문제를 공유한다.
• 모든 부분 문제를 한번만 계산하고 그 결과를 저장하고 재사용한다.
• 상향식 방법으로 접근한다.

DP 풀이방법

1. 문제를 부분 문제로 분할한다.
2. 점화식으로 정의한다.
3. 가장 작은 부분 부터 해를 구하고 테이블에 저장한다. 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.

---

예시문제

• 피보나치 : 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조이다.
• 동전 거스름 돈 구하기 : 최소 동전 줘야함 (배수가 아닐경우) 1 4 6원이 있을 경우
• 계수 값 구하기
• 도둑가방 문제 : 10kg용량에 4가지 선물 중 최대가치를 위해서는
• 이항 계수

Ksapsack 알고리즘

public class DP4_kanpsack간단하게 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int W = sc.nextInt();
		
		int[] weights = new int[N+1];
		int[] profits = new int[N+1];
		
		for (int i = 1; i <= N; i++) {
			weights[i] = sc.nextInt();
			profits[i] = sc.nextInt();
		}
		
		int[] DP = new int[W+1];
		//1차원으로
		for (int i = 1; i<=N; i++) {
			//ㅈ자신의 무게 까지 , 뒤쪽부터
			for ( int w = W; w >= weights[i]; w ++) {
				DP[w] = Math.max(DP[w], profits[i] + DP[w-weights[i]]);				
			}			
		}
		System.out.println(DP[W]);		
	}
}

최장 증가 수열의 길이

• DP방법 : L[i] = i(자신)를 마지막으로 하는 최장 길이
• DP방법2 : L[i] = i(자신)를 길이로하는 가장 작은 끝 값

모든 쌍 최단 경로

• (유의)최장경로 문제는 최적의 원칙이 적용되지 않는다.

모든 쌍 최단 경로 : 브루트 포스

• BFS(가중치없는 그래프) / 다익스트라(가중치있고)
• 한정점에서 달느 정점으로 모든 경로를 구함 -> 최단경로를 찾음
• 최악이다

모든 쌍 최단 경로 : 플로이드 워셜 알고리즘

• 다익스트라는 N^3나온다. 플로이드도 같다.
• A -> B 의 최단경로를 찾을 때 다음 둘 중 하나이다.
  1. A -> B 직접 가기
  2. A -> ... -> 돌아서 가기
• 경유지 하나를 고정하고, 모든 쌍의 경유지를 고려한다.
• 경유 - 출발 - 도착 으로 3중 for문 작성하면된다.

D[a][b] = Min ( D[a][k] + D[k][b] , D[a][b] )