Dynamic Programming

chaming·2021년 1월 5일

dynamic programming

알고리즘 개념알기

목록 보기

1/8

Dynamic Programing란?

💡가장 간단하게 말하자면 점화식을 구하여 반복적으로 계산하는 것이다.
이전에 사용된 값을 재사용하는 것이라고 이해하면 쉽다.

피보나치수열이 가장 쉽고 빠르게 이해할 수 있는 예제라고 생각한다.

피보나치 수열이란 1,1,2,3,5,8,13,...... 와 같이 이전의 두 항을 더하여 만드는 수열이다.
따라서 f(n) = f(n-1) + f(n-2) 계산식을 이용하여 구할 수 있다.

// 재귀함수 이용(recursive)
public static int fibo(int n){
	if(n == 1 || n ==0 ){
    	return 1;
    }
    return fibo(n-1)+fibo(n-2);
}

위와 같은 식은 간단한 계산은 문제 없겠지만,
🤦‍♀️fibo(10) 함수를 재귀적으로 호출하면서, 숫자가 커짐에 따라 Stack OverFlow가 발생한다.

이러한 문제점을 Dynamic Programing 기법으로 해결할 수 있다.
🙆‍♀️ fibo()함수의 호출을 최소화시켜, 이미 계산된 적이 있다면 값을 불러와서 재사용할 수 있도록 코드를 수정해보자.(이해를 돕기위해 아주 간단하게 막쓴 코드이다..)

// DP를 이용한 피보나치 수열
public static int[] fibo = new int[10];			// dp를 사용하기 위해 int[] 배열을 선언

public static int fibo(int n){
    fibo[0] = 1;
    fibo[1] = 1;
    for(int i=2; i<=n; i++){
    	// 식을 이용하여, 이전에 사용했던 계산식을 재활용한다.
        // 이것을 memoization이라고 할수 있다.
    	fibo[i] = fibo[i-1] + fibo[i-2];
    }
    return fibo[n];
}

👀그렇다면, Dynamic Programing이 무조건 재귀함수를 호출하는 방법보다 더 좋을까?

1. 시간복잡도 : DP O(n^2) < recursive O(2^n)
시간 복잡도를 살펴본다면 DP가 훨씬 빠르다.

2. 공간복잡도 : DP > recursive
DP의 경우 메모리공간을 차지한다.
memoization기법을 사용하므로 계산이 된값을 저장해 놓고 있다가, 필요한 경우 중복계산 없이 호출한다. 위의 간단한 예제만 살펴보아도 int[]와 같이 어딘가에는 값을 저장하고 있어야하기 때문이다.

그렇다면 이제 조금 더 자세히 DP에 대해 알아보자.

DP 알고리즘 종류

다익스트라 알고리즘

하나의 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

플로이드 와샬(Floyd Warshall) 알고리즘

모든 최단 경로를 구하는 알고리즘
모든 정점에서 모든 정점으로의 최단 경로를 구하는 경우

좀 더 자세한 내용은 ▶▶▶ Floyd Warshall 알고리즘

DP 접근방식

계속 피보나치 수열로 설명을 해본다.

메모이제이션(memoization)

DP = 메모이제이션은 아니다.
하지만, 메모이제이션의 개념으로 이해하기 쉬울거 같아서 함께 설명한다.

계산된 값을 버리지않고 저장한다는 뜻.
계산된 값을 저장해두고 있다가 필요한 경우 호출해서 사용하는것이다.
이렇게 저장되는 배열을 '캐시'라고 하며, 중간에 저장하는 것을 '캐싱한다'라고 표현한다.

TopDown

재귀함수이다.

fibo(10)을 구한다면, fibo(9), ffibo(8) 큰 수에서 작은 수의 방향으로 계속 재귀적으로 호출하는 방법을 말한다.

public int[10] fibo = {0,};		// 배열을 0으로 모두 초기화

public class int fibonachi(int n){
	if(n <2){		// fibo[0] , fibo[1] = 1;
    	return 1;
    }
    
    if( fibo[n] == 0){
    	fibo[n] = fibo[n-1] + fibo[n-2];
    }
    return fibo[n];
}