알고리즘 개념 - 동적계획법(DP)

✍DP Algorithm

"동적계획법(Dynamic Programming) 이란 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다."

'분할 정복'도 큰 문제를 작은 문제로 나누어 푸는 것이 동적 계획법과 같은데 이는 계산한 부분문제를 한번만 쓰고 더이상은 쓰지 않는다. 따라서 분할정복은 부분문제의 계산결과를 저장하는 메모이제이션을 하지 않는다.

반면 동적계획법은 부분문제의 중복계산을 피하기 위해서 계산결과를 저장해두는 메모이제이션을 한다. 이 점이 분할 정복과의 차이점!
시간복잡도가 줄어드는 장점이 있다.

👆Bottom Up 방식

for문을 이용해서 처음값부터 다음값을 계산해 나가는 방식이다.
재귀의 방식을 활용하기도 함.

for문을 이용해서 계산

	public static int fib3(int num) { //bottom-up dp
		memo[0] = 0;
		memo[1] = 1;
		for( int i = 2 ; i <= num ; i++) {
			memo[i] = memo[i-1] + memo[i-2];
		}
		return memo[num];
	}

👇Top Down 방식

재귀와 같은 방식.
위에서 아래로 내려오는 방식이다.
함수 호출을 줄이기 위해, 메모이제이션을 사용한다.

일반 재귀

	public static int fib(int num) {
		if( num <= 0 )return 0;
		else if ( num ==1) return 1;
		else return fib(num-1) + fib(num-2);
	}

메모이제이션 적용 Top-Down DP

	public static int fib2(int num) {
		if( num <= 0 )return 0;
		else if ( num ==1) return 1;
		if(memo[num]!=0) {
			return memo[num];
		}
		memo[num] = fib2(num-1) + fib(num-2);
		return memo[num];
	}