동적 계획법🗓️ (Dynamic Programming)

❓공부하게 된 계기

➡️ 다음주 알고리즘 스터디 주제인 DP 에 대해서 예습

❗️공부한 내용

1️⃣ Dynamic Programming 이란?

➡️ 디자인 패러다임 중 하나로 잡한 문제를 여러 개의 작은 부분 문제로 나누어 해결하는 방법이다.

➡️ Dynamic 은 '기억하기' & Programming 은 '나누기' 정도 생각하는게 좋다.

➡️ 동적 계획법의 핵심인 Memorization(DP 구현 방법 중 하나) 을 이용해 빠른 속도로 최적의 해를 찾아내는 것이 목표이다.

2️⃣ DP 문제가 성립할 조건

➡️ DP 문제가 성립하기 위해서는 크게 2개의 조건을 만족해야한다.

① 최적 부분 구조 (Optional Substructure)
➡️ 상위 문제를 하위 문제로 나눌 수 있으며, 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다.
② 중복되는 부분 문제 (Overlapping Subproblem)
➡️ 동일한 작은 문제를 반복적으로 해결해야한다. (단 같은 문제는 구할 때마다 정답이 같다.)

3️⃣ 문제 예시 (피보나치)

➡️ DP 를 이해하기 위해 가장 좋은 문제는 피보나치 수열이다.

public class Simple {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		System.out.println(fibo(n));
	}
	
	// 단순 재귀
	static int fibo(int x) {
		if( x ==1 || x==2) return 1;
		return fibo(x-1) + fibo(x-2);
	}
}

피보나치 재귀 함수 동작 방식 (출저 : https://loosie.tistory.com/150)

➡️ ① f(6) 의 큰 문제가 계속 쪼개져 작아지고, ② f(3) 와 f(2) 등이 계속해서 반복되므로 DP 조건을 모두 확인하는 것을 볼 수 있다.

4️⃣ DP 구현 방식

➡️ DP 구현 방식에는 크게 Top-down (하향식) 과 Donw-top (상향식) 이 있다.

① Top-down (하향식)

➡️ 상위 문제를 해결하기 위해 하위 문제를 재귀적으로 호출한 다음, 작은 문제에서 해결한 값을 저장 및 기억 (Memorization) 한다. 이후 올라가면서 해당 값들을 재활용하면서 문제를 해결한다.

➡️ 구조적으로는 이해하기 쉽지만, 재귀 호출을 사용하기 때문에 Stack Overflow 의 문제가 발생할 수 있다.

public class Topdown {
	// Memorization 을 위한 배열 생성
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		System.out.println(fibo(n));
		
	}
	
    // Top-down
	static int fibo(int x) {
		if( x ==1 || x==2) return 1;
		// (1) 이미 해결한 문제면 재활용
		if(dp[x] != 0) return dp[x];
		// (2) 해결되지 않은 문제면 재귀 호출하여 값 저장
		dp[x] = fibo(x-1) + fibo(x-2);
		return dp[x];
	}
}

② Donw-top (상향식)

➡️ 전형적인 DP 의 형태로, 가장 작은 문제부터 시작하여 값을 저장하고 이 값들을 기반으로 다음 문제를 순차적으로 해결하는 방식.

➡️ 구조 특성상 반복문을 사용한다.

public class Bottomup {
	// 값을 저장하기 위한 배열 생성
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		
		System.out.println(fibo(n));
	}
	
    // Bottom-up
	static int fibo(int x) {
		dp[1] =1;
		dp[2] =1;
        // 바로 바로 값을 저장 & 사용
		for(int i=3; i<x+1; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[x];
	}
}

✏️ 적용 시켜본 예제

🧐 추가로 궁금한 점

1️⃣ 분할 정복과 다른 점

➡️ 분할 정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않지만, DP 는 겹치는 문제가 발생한다. 겹치는 문제를 계속 풀게되면 비효율적이므로 Memorization 기법을 통해 문제를 따로 저장해두었다가 겹치는 문제가 발생하면 바로 값을 사용한다.

분할 정복과 DP 의 차이 (출저 : https://loosie.tistory.com/150)

 

➡️ 하위 문제가 독립적이지 않고 중복이 되는 경우에는 DP 가 더 나은 시간 복잡도를 가지만, 분할정복 문제에서는 하위 문제는 독립적으로 구성되어있기 때문에 반복적으로 계산이 되지 않는다.

🔗 참고

[알고리즘] 동적계획법 DP (Dynamic Programming) 정리 (Java)

 

[Java]동적 계획법(Dynamic Programming)