DP(Dynamic Programming)

다이나믹 프로그래밍이란? 

: 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

 

> 여러 개의 하위 문제로 나누어 풀고 저장한다. 그것을 결합하여 최종적인 목적에 도달한다. 

> 나중에 같은 하위 문제가 나왔을 경우 간단히 해결 가능하고, 계산 횟수를 줄일 수 있다. 

 

<조건>

1) 최적 부분 구조 : 큰 문제의 최적해가 작은 문제의 최적해를 포함해야 한다. 그래야 작은 문제의 최적해를 구한다음 그것을 활용하여 큰 문제의 최적해를 구할 수 있으니까~~

2) 중복 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다. 

---

ex. 피보나치 수열

~> 0과 1로 시작하고 이전의 두수 합을 다음 항으로 하는 수열. (n은 자연수)

fib(0) = 0, fib(1) = 1

 

ver 1. 재귀함수

public static int fib(int n) {
	if (n==0 || n==1) {
    	return n;
    }
    return fib(n-1) + fib(n-2);
}

>> 재귀함수가 반복되기 때문에 자연수 n이 커지면 커질수록 지수적으로 계산량이 증가한다. 

 

ex. fib(7)을 구하려면 fib(5)와 fib(6)을 구해야하고, fib(6)을 구하려면 fib(5)와 fib(4)를 구해야한다... 결국 fib(1)과 fib(0)을 만날 때까지 계속 쪼개지면서 부분 문제가 중복이 된다. 

 

~~> 그러면 중복될 것 같은 문제들을 처음 풀 때 값을 저장해두고, 다음 풀 때 그 값을 불러오기만 하면 훨씬 시간이 단축된다. 

그래서 동적 계획법을 사용하는 것!!

 

저장은 저장소(cache)를 만들어 저장한다. 

 

 

 

1) 재귀적 풀이 (recursive)

• Top-down 방식 : 재귀 호출과 메모이제이션을 사용

* 재귀 : 자기 자신을 호출하는 함수로 반복적으로 호출함으로써 원하는 결과를 도출한다.

* 메모이제이션(memoization) : 중복 계산을 피하기 위해 이전에 계산된 결과를 저장하고 동일한 계산에 저장된 결과를 이용한다. >> 일반적으로는 해시테이블/배열 등을 사용하여 구현함. 

 

ver2. 해시맵에 저장

private static Map<Integer, Integer> memo = new HashMap<>(); //해시맵에 저장(메모이제이션)

public static long fibo(int n) {
	if (n<=1) { //n==1일때 혹은 n==0일때 n도출
    	return n;
    } 
    if (memo.containsKey(n)) { //해시맵에 n이 키인 것이 저장되어 있다면 
    	return memo.get(n); // 그 밸류값을 도출
    } 
    int result = fibo(n-1) + fibo(n-2); // 결과값을 할당하여
    memo.put(n, result); //n을 키로, 결과값을 밸류값으로 저장. 
    return result;
    }
}

 

ver3. int 배열에 저장

public static int[] dp = new int[100]; //저장할 배열의 크기가 정해져있다. 

public static int fib(int n) {
	if (n<=1) {
    	return n;
    }
    if (dp[n] !=0) { //이미 저장된 dp라면 초기화값인 0이 아니기 때문에
    	return dp[n]; // 저장된 값을 도출
    }
    dp[n] = fib(n-1) + fib(n-2);
    return dp[n];
}

 

👀 스택 오버플로우 발생 가능성이 있다..(재귀 호출이 지나치게 많이 일어날 때 발생)

 

 

2) 반복적 풀이 (iterative)

• Bottom-up : 작은 문제부터 해결하여 ~> 큰 문제까지 해결하는 알고리즘 방식. 
• 반복문을 사용.

ver4. 반복문 사용

public static int fibo (int n) {
	if (n<=1) {
    	return n;
    }
	int dp[] = new int[n+1]; // 저장할 배열 
    dp[0] = 0; //n==0일 때 초기값 설정
    dp[1] = 1; //n==1일 때 초기값 설정
    for(int i=2; i<=n; i++) {
    	dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

 

👀 초기값을 설정해줘야 하고, 작은 문제들의 결과값을 임시적으로 저장할 공간이 필요하다..