[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

목차

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

다이나믹 프로그래밍 (Dynamic Programming) 또는 동적 계획법은 큰 문제를 작은 문제로 쪼개서 푸는 기법이다. 다이나믹 프로그래밍의 특징은 모든 작은 문제들은 단 한 번만 풀어야 한다는 것이다. 한 번 푼 것을 여러 번 다시 푸는 일이 없어 비효율적인 알고리즘을 개선시키는 방법 중에 하나다. 따라서 이미 정답을 구한 작은 문제의 결과는 따로 배열에 저장하고 나주에 필요할 때 다시 사용한다. 이것을 메모이제이션 (Memoization)이라고 한다. 그리고 다시 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞에서 메모한 작은 문제의 결괏값을O(1)의 시간복잡도로 이용해서 문제를 효율적으로 풀 수가 있다.

 

다이나믹 프로그래밍 접근 방법

다이나믹 프로그래밍의 접근 방법은 크게 두 가지: Bottom-up과 Top-down으로 나뉜다. Bottom-up은 작은 문제부터 구해 나아가서 큰 문제를 해결하는 방법이고 Top-down은 재귀 함수를 이용해서 큰 문제를 풀 때 작은 문제를 필요로 할 때 그때서야 작은 문제를 해결하는 거다. 보통 Top-down은 재귀 함수를 이용하는 거고 Bottom-up 방법은 for문을 이용해서 답을 도출한다. Top-down과 Bottom-up 둘중에 뭐가 더 좋은지는 따로 없고 자기 자신한테 더 편한 방법으로 문제를 풀면 된다. 나는 개인적으로 Bottom-up 방식을 더 선호한다.

 

 

다이나믹 프로그래밍 예시

이 두가지 방법이 어떻게 다른지는 유명한 피보나치 문제로 한번 보겠다. 피보나치 수열은 특정한 수를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구하는 문제다.

점화식으로 나타내면 fib(1) = 1, fib(2) = 1, fib(i) = fib(i-1) + fib(i-2), 단, i >= 2로 나타낼수 있다.

 

이 공식을 따라서 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...로 나아갈 수 있다. 만약에 15번째 피보나치 수열(fib(15))을 구하려면 fib(14) 와 fib(13)을 알아야 한다. 그리고 fib(14)를 알려면 fib(13)과 fib(12)를 알아야 한다. 따라서 fib(15)를 구하려면 밑에 있는 그림에 나와있는 과정을 따르게 된다. 그래서 재귀 함수로 구할 때 이미 구한 값들을 반복적으로 또 구해서 매우 비효율적이다. 여기서 다이나믹 프로그래밍 기법을 이용하면 더욱더 효과적으로 구할 수 있다.

 

 

 

 

단순 재귀 코드

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

 

 

Bottom-up 방식 Java

public class Main {
  static long[dp];

  public static void main(String[] args) {
    dp = new long[1000];
    dp[1] = 1;
    dp[2] = 1;
    int n = 50;   //구하고 싶은 n번째 피보나치 수
    nth_fib = fibonacci(n);
  }

public static long fibonacci(int n) {
  if (n == 1 || n == 2) return 1;
  for (int i = 3; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

 

 

 

Top-down 방식 (Java)

public class Main {
  static long[dp];

  public static void main(String[] args) {
    dp = new long[1000];
    dp[1] = 1;
    dp[2] = 1;
    int n = 50;   //구하고 싶은 n번째 피보나치 수
    nth_fib = fibonacci(n);
  }

public static long fibonacci(int n) {
  if (n == 1 || n == 2) return 1;  // 종료 조건 (1 이나 2일 때 1 반환)
  if (dp[n] != 0) return dp[n];   //이미 계산한 적이 있는 수면 그대로 반환
  return dp[n] = fibonacci(n-1) + fibonacci(n-2);   //한번에 저장하면서 값 반환
}

 

피보나치 수열을 단순 재귀 함수로 풀었을 때 중복되는 문제를 여러 번 계산하기 때문에 O(2ⁿ)의 시간 복잡도가 소요된다. 하지만 다이나믹 프로그래밍으로 문제를 풀었을 때는 계산한 값들을 따로 저장하고 다시 사용하므로 O(n)의 시간 복잡도가 소요된다.

만약에 n=25이고 단순 재귀함수를 썼었으면 약 2^25 = 33554432의 연산을 했고 다이나믹 프로그래밍을 이용했을 때는 25번의 훤씬 더 적은 연산 횟수를 볼 수 있다. 따라서 효율면에서는 다이나믹 프로그래밍이 훨씬 더 효율적이다.

 

다이나믹 프로그래밍의 유형

다이나믹 프로그래밍 안에서도 자주 이용하는 여러 가지 유형들이 있다.

EX)

- 가장 긴 증가하는 부분 수열 : LIS (Longest Increasing Subsequence)

최장 공통 부분 수열 : LCS (Longest Common Subsequence)

배낭 문제 : knapsack problem

등등이 있다.

이 유형들은 나중에 차차 올리도록 하겠다.