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

1. DP란?

DP(Dynamic Programming)은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로, 이미 했던 연산이 반복되는 결점을 보완하기 위해서 고안되었다.

 

피보나치 수열에서 사용되는 일반적인 재귀 방식도 DP와 매우 유사하지만, 일반적인 재귀 방식은 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수도 있다는 것이다.

 

Dynamic Programming 문제를 풀기 위한 방법에는 Top-Down과 Bottop-Up 방식이 있는데, 아래에서 알아보겠다. 

---

2. Dynamic Programming 구현

2-1 Top-Down 방식

Top-Down 방식이란 재귀 함수로 다이나믹 프로그래밍을 구현하는 방식이며,

말 그대로 문제 풀이가 위에서 아래로 진행된다.

예를 들어 n에 6을 대입하면 fibonacci(6)부터 차례대로 return fibonacci(5) + fibonacci(4) ... 으로 1과 0까지 도달하는 방식이다.

=> 가장 큰 문제를 방문 후 작은 문제를 호출 하여 답을 찾는 방식

 

피보나치 수열을 일반적인 재귀 함수로 구현하면 아래와 같다.(시간복잡도 O(N^2))

int fibonacci(int n)
{
  if ( n <= 1 ) {
    return n;
  }
   
  return fibonacci(n-1) + fibonacci(n-2);
}

 

자 그러면 위와 같은 일반적인 재귀함수를 DP의 Top-Down 방식으로 변경해보자.

일반적으로 재귀를 사용하는 구조는 같지만, 부분 문제에서 구한 값을 기억(Memoization)하면서 다음 재귀에서 재활용하는 과정을 추가해주면 된다.

 

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

	public static void main(String[] args) {
	
		int n = n번째 피보나치 수를 구하기 위한 숫자;
		dp = new long[n + 1];

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


    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);
        }
	}
}

   

이렇게 부분 문제에서 해결한 값을 저장(Memoization)하면서 문제를 해결하는 경우엔 불필요한 계산 과정을 줄여주기 때문에 시간복잡도 O(N)의 엄청난 속도 향상을 보일 수 있다.

---

2-2 Bottom-Up 방식

Bottom-Up방식이란, 단순히 반복문으로 다이나믹 프로그래밍을 구현하는 방식이고, DP테이블을 활용한다.

Top-Down방식과 동일한 원리이지만, 단순히 반복문을 이용하는 방식이다.

=> 다이나믹 프로그래밍의 전형적인 형태

 

마찬가지로, 피보나치 수열을 구하는 함수를 DP 테이블을 활용한 Bottom-UP방식으로 구현하면 아래와 같다.

public class Main {
	// DP 테이블 생성
	static long[] dp;

	public static void main(String[] args) {
	
		int n = n번째 피보나치 수를 구하기 위한 숫자;
		dp = new long[n + 1];

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


    static long Fibonacci(int n) {
        // 기저 조건(피보나치 수열의 초항).
        dp[0] = 0;
        dp[1] = 1;
        
        # 피보나치 함수(Fibonacci Function) 반복문으로 구현(Bottom-Up 방식)
        for(int i = 2; i < n+1; i++) {
            dp[i] = dp[i-1] + dp[i-2]; 	
        }
        return dp[n];
    }
}

 

이처럼, Bottom-Up 방식은 작은 문제부터 차례로 답을 구해나가는 방식이다.

 

 

📗참고사이트

동적 프로그래밍 DP(Dynamic Programming - top- down, bottom-up)

[Algorithm] Top-Down, Bottom-Up 이란?

Top-down(탑다운) vs Bottom-up(바텀업)

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

알고리즘 - Dynamic Programming(동적 계획법)