DP (Dynamic Programming, 동적계획법)

하위 문제의 해를 이용하여 상위 문제의 해를 효율적으로 구하는 기법

'분할정복' 과의 차이

• 동적 계획법은 부분문제 사이에 연관성이 존재하고, 분할정복은 부분문제 사이에 연관성이 없다.
• 동적 계획법은 부분문제가 중복되고, 분할정복은 부분문제가 중복되지 않는다.

구현 방식

• Top-Down 방식과 Bottom-Up 방식이 있는데, 각 방식이 압도적 우위를 가지는 장단점은 명확하지 않다.
• Top-Down
  • 전체문제에서 가장 작은 부분문제까지 호출한 뒤, 가장 작은 부분문제부터 해결값을 기억(Memoization)하고 재활용하면서 전체문제를 해결하는 방식
  • 재귀를 주로 사용함. -> 메모리 문제 주의
• Bottom-up 
  • 가장 작은 부분문제부터 호출해가며 해결값을 기억(Tabulation)하고 재활용하면서 전체문제를 해결하는 방식.
  • 반복문을 주로 사용함.

• Tabulation? : Tabulation의 사전적 정의는 '도표 작성'이다. 문제 해결 방식이 표를 채워나가는 것과 유사하다고 하여 붙여진 이름이다. 따라서 Bottom-up방식을 사용하는 경우는 Memoization이라고 부르지 않고 Tabulation을 활용하여 값을 재활용한다고 이해하면 된다.

 

피보나치 문제의 Top-Down 코드

import java.util.Scanner;

public class FibonacciNumber_TopDown {
	// Memoization을 적용할 배열.
	static long[] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp = new long[n + 1];

		// n번째 피보나치 수를 구하고 출력하라.
		System.out.println(Fibonacci(n));
		sc.close();
	}

	private static long Fibonacci(int n) {
		// 기저 조건(피보나치 수열의 초항).
		if (n == 1 || n == 2) {
			return dp[n] = 1;
		}
		// 만일, 저장된 값이 존재하는 경우 기억된 값을 바로 넘겨준다.
		if (dp[n] != 0) {
			return dp[n];
		}
		// 그렇지 않은 경우, 기저 조건까지 내려가서 구해진 값을 저장하면서 재귀를 전이한다.
		else {
			return dp[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
		}
	}
}

 

피보나치 문제의 Bottom-Up 코드

import java.util.Scanner;

public class FibonacciNumber_BottomUp {
	// Tabulation을 적용할 배열.
	static long[] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp = new long[n + 1];
		// 기저 조건을 바탕으로 초항을 먼저 초기화 해둔다.
		dp[1] = 1;
		dp[2] = 1;

		// n번째 피보나치 수를 구하고 출력하라.
		System.out.println(Fibonacci(n));
		sc.close();
	}

	private static long Fibonacci(int n) {
		// 기저 조건을 기반으로 테이블을 채워나간다(Tabulation).
		for(int i = 3; i <= n; i++) {
			// 점화식을 이용하여 쉽게 구할 수 있다.
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		
		return dp[n];
	}
}

-> 배열이 아닌 일반 변수로도 가능하다.

 

문제 접근 방식

1. 부분문제로 나누고 부분문제의 답을 저장할 테이블을 정의해본다.
2. 부분문제 사이의 관계를 생각하여 점화식을 도출한다.
3. 점화식을 기반으로 부분문제 테이블을 갱신해가며 전체문제를 해결한다.

 

다이나믹 프로그래밍 문제에 접근하는 방법

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다
• 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있다
  • 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해 보자
• 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이
  큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다
• 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다

 

 

참고한 곳
https://freedeveloper.tistory.com/276
https://sskl660.tistory.com/87