---

⚡ 동적 계획법(Dynamic Programming)

---

📌 메모이제이션

🔷 재귀함수의 중복 호출은 프로그램의 성능을 급격히 떨어뜨린다.

• ex) 피보나치 수열 함수 구현

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

🔷 메모이제이션(Memoization)

• 컴퓨터 프로그램을 실행할 때, 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술
• 동적 계획법의 핵심이 되는 기술
• 피보나치 수열 함수의 실행시간을 O(n)으로 만들 수 있다.

static int [] memo = new int [100];
	
static {
	memo[0] = 0;
	memo[1] = 1;
}
	
static int fibo(int n) {
	if(n > 1 && memo[n] == 0) 
		memo[n] = fibo(n-1) + fibo(n-2);
		
	return memo[n];
}

💡 n에서부터 0까지 내려가면서 접근하므로 이는 하향식 접근방법이다.

🔷 단점

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

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

---

📌 동적 계획 알고리즘

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

💡 최적화 문제
최적(최대값이나 최소값 같은)값을 구하는 문제
해당 문제에 여러 해가 있을 수 있다.

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

🔷 동적 계획법을 적용하려는 문제는 필히 다음과 같은 요건들을 가지고 있어야한다.

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

• DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고, 작은 문제들의 최적해를 이용하여 순환적으로 큰 문제를 해결한다.

  💡 순환적인 관계를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적 도구인 점화식을 사용한다.

• DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간(Table)에 저장하게 된다.
• 그리고 이렇게 저장된 해들이 다시 필요할 때 마다 해를 얻기 위해 다시 문제를 재계산하지 않고, table의 참조를 통해서 중복된 계산을 피하게 된다.

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

• 주어진 문제가 최적화의 원칙을 만족해야만 동적 계획법을 효율적으로 적용할 수 있다.

💡 최적화의 원칙
어떤 문제에 대한 해가 최적일 때, 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다.

• 동적 계획법의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적해들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법을 적용할 수 없다.

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

분할 정복	동적 계획법
연관 없는 부분 문제로 분할	부분 문제들이 연관이 없으면 적용 불가
같은 부분 문제가 나타나면 다시 계산	모든 부분 문제를 한번만 계산하고, 결과를 저장하고 재 사용
하향식 방법으로 접근	상향식 방법으로 접근
부분 문제들 사이에 관계가 없어도 상관없음	부분 문제들 사이에 의존적 관계가 존재

🔷 3단계 DP 적용 접근 방법

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

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

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

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

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

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

static long fibo(int n) {
	long [] dp = new long[n+1];
	dp[0] = 0;
	dp[1] = 1;
		
	for(int i = 2; i <= n; i++) {
		dp[i] = dp[i-2] + dp[i-1];
	}
		
	return dp[n];
}

💡 DP 알고리즘이 수행속도가 훨씬 빠르며 반복문을 사용하기 때문에 함수 호출이 발생하지 않는다.

---

📌 DP 적용 문제

⭐ 동전 거스름 돈

🔷 부분 문제 정의

• C[i][j] = Di 동전으로 j원 거슬러 줄 때의 최적 (Di1 = 1, Di2 = 4, Di3 = 6)

🔷 최적화 원리

• 부분문제를 보면, 만약 i번 동전으로 j원을 거슬러 줄 때 최적으로 거슬러 주지 않는다면, 전체 문제의 거스름 돈의 개수도 최적이 되지 않는다.

🔷 점화식

• C[i][j] = min(C[i][j-Di] + 1, C[i-1][j]) -> O(i * j)

import java.util.Scanner;

public class DailyAPS {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int money = sc.nextInt(); //해당 거스름돈에 대한 최소 동전 개수를 구하고 싶다.
		//사용할 수 있는 동전은 3가지: 1원 / 4원 / 6원
		
		int [] dp = new int [money+1];
		dp[0] = 0;
		
		for(int i = 1; i <= money; i++) {
			int min = Integer.MAX_VALUE; //i원에 대한 거스름돈의 최소 개수
			//1원을 작은 부분문제에 추가
			min = Math.min(min, dp[i-1]+1);
			//4원을 작은 부분문제에 추가
			if(i>=4)
				min = Math.min(min, dp[i-4]+1);
			//6원을 작은 부분문제에 추가
			if(i>=6) 
				min = Math.min(min, dp[i-6]+1);
			
			dp[i] = min;
		}
		
		System.out.println(dp[money]);
	}
}

---

⭐ 0-1 Knapsack (배낭 문제)

🔷 n개의 물건과 각 물건 i의 무게 wi와 가치 vi가 주어지고, 배낭의 용량은 W일 때, 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제

• 배낭에 담은 무게의 합이 W를 초과해서는 안됨.
• 물건은 반드시 한 개씩만 존재.

❗ 물건과 물건의 무게는 부분 문제를 정의할 때 반드시 필요하다. 왜냐하면 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는 것과 안 담는 것을 현재 배낭에 들어있는 물건의 가치의 합에 근거하여 결정해야 하기 때문이다.

🔷 부분 문제간의 함축적 순서

• K[i-1, w - wi]와 K[i-1, w]가 미리 계산되어 있어야만 K[i, 2]를 계산할 수 있다.

import java.util.Scanner;

public class DailyAPS {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(input);

		int N = sc.nextInt(); //물건의 개수
		int W = sc.nextInt(); //가방의 무게
		
		int [] weights = new int [N+1];
		int [] cost = new int[N+1];
		
		for(int i = 1; i <= N; i++) {
			weights[i] = sc.nextInt();
			cost[i] = sc.nextInt();
		}
		
		int [][] dp = new int [N+1][W+1];
		//물건을 하나도 고려하지 않았을 때는 이미 0으로 초기화 되어있음
		//물건을 하나씩 고려하면서 처리
		for(int i = 1; i <= N; i++) {
			//i번째 물건까지 고려를 한 경우가 저장
			//w: 임시 배낭의 크기
			for(int w = 0; w <= W; w++) {
				if(weights[i] <= w) {
					//해당물건 판단
					//현재 해당 무게에서의 최적해는 dp[i-1][w]
					//이번에 물건을 고려한 최적해는 dp[i-1][w-weights[i]] + cost[i]
					//위의 두가지의 경우 중 베스트 값을 현재 저장
					dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-weights[i]] + cost[i]);
				} else {
					dp[i][w] = dp[i-1][w]; //현재 고려할 물건의 무게가 임시무게를 벗어나 고려할 수 없을 때
				}
			}
		}
		
		System.out.println(dp[N][W]);
	}
	
	public static String input = "4 10\r\n" + "5 10\r\n" + "4 40\r\n" + "6 30\r\n" + "3 50\r\n" + "";
}

---

큰 벽이 느껴지지만 뭐 못할 정도는 아닌 것 같다...