알고리즘) 다이나믹 프로그래밍(Dynamic Programming)이 무엇인가?

# 다이나믹 프로그래밍 : 큰 문제를 작은 나눠서 푸는 방식의 프로그래밍

 

# 큰 문제를 작은 나눠서 푸는 방법 2가지 : 다이나믹 프로그래밍(Dynamic Programming), 분할 정복 알고리즘(Divide & Conquer)

 

# 다이나믹 프로그래밍으로 풀 수 있는 문제들이 갖는 2가지 속성 : Overlapping Subproblem, Optimal Substructure

 

1. Overlapping Subproblem(겹치는 부분 문제) 

 - 큰 문제의 부분 문제들의 중복이 존재해야 한다.

 - 문제들이 겹치므로 큰 문제는 부분 문제들을 푸는 방법과 같은 방법으로 풀 수 있다. -> 주로 재귀를 사용

 

2. Optimal Substructure(최적 부분 구조) 

 - 큰 문제의 정답을 부분 문제의 정답을 통해 구할 수 있다.

 - 문제의 크기에 상관 없이 어떤 한 문제의 정답은 일정해야 한다.

 

ex) 피보나치 수를 구하는 방법 : F(n) = F(n-1) + F(n-2)

   큰 문제 : F(n), 부분 문제 : F(n-1), F(n-2)

   1. Overlapping Subproblem : F(n)을 구하기 위해 필요한 부분 문제 F(n-2)는 F(n-1)을 구하는데 필요한 부분 문제이기도 하다.(중복됨)

   2. Optimal Substructure : 부분 문제인 F(1)과 F(0)을 풀면 큰 문제인 F(2)를 풀 수 있고, 부분 문제인 F(n-1)과 F(n-2)를 풀면 큰 문제인 F(n)을 풀 수 있다.

 

# 다이나믹 프로그래밍의 방법 : 부분 문제들을 해결해서 얻은 답을 기록해둔다.(다시 연산할 필요가 없도록) -> Memorization

피보나치를 예로 들면 F(n)을 구하기 위해 F(0), F(1), ..., F(n-2), F(n-1)의 답들을 기록해둔다.

 

5번째 피보나치 수를 구하면서 풀게되는 부분 문제들이다. 

그림을 보면 중복되는 부분 문제들이 존재하는 것을 확인할 수 있다.

중복되는 부분 문제들을 맞닥뜨릴 때마다 연산하지 않고, 전에 풀고 기록해둔 답을 가져와서 쓴다면 큰 문제를 해결하는데 소요되는 시간을 줄일 수 있다.

public class Doodle {
    int[] memo = new int[100]; // memorization을 위한 기록 배열
    int fibonacci_with(int n) { // memorization 사용
        if (n <= 1) {
            return n;
        } else {
            if (memo[n] > 0) { // 전에 푼적이 있는 작은 문제라면
                return memo[n]; // 또 풀지 말고 기록해두었던 답을 가져와서 사용
            }
            memo[n] = fibonacci_with(n-1) + fibonacci_with(n-2);
            return memo[n];
        }
    }

    int fibonacci_without(int n) { // memorization 사용하지 않음
        if (n <= 1) {
            return n;
        } else {
            return fibonacci_without(n-1) + fibonacci_without(n-2);
        }
    }
}

위 함수는 memorization을 사용한 것, 아래 함수는 사용하지 않은 것임.

memorization을 사용하지 않은 알고리즘의 경우, 큰 문제를 1개 해결하기 위해 부분 문제 2개를 풀어야 하고 각 부분 문제를 풀기 위해서도 2개의 부분 문제를 풀어야 한다. 결국 n번째 피보나치 수를 구하기 위해서는 2*2*2*... = 2^n 만큼 문제를 푸는 연산을 해야 한다.

문제 1개를 푸는데 걸리는 시간이 O(1)이므로 

총 O(2^n)의 시간복잡도를 갖는다.

반면, memorization을 사용한 알고리즘의 경우, n번째 피보나치 수를 구하기 위해 문제 해결 연산을 n번만 수행하면 된다. 부분 문제들이 중복된다 하더라고 1번 연산을 수행했으면 그 답을 기록한 것을 사용하면 되기 때문이다. 

결국 총 O(n)의 시간복잡도를 갖는다.

memorization을 사용하지 않은 알고리즘에 비해 월등히 빠른 것을 확인할 수 있다.

 

# 다이나믹 프로그래밍의 구현 방식

1. Top-Down : 큰 문제를 조금씩 작게 만들어가는 것

 - 큰 문제부터 문제를 쪼개가면서 부분 문제들로 만드는 것을 반복하여, 부분 문제를 푸는 것으로 큰 문제를 해결

2. Bottom-Up : 작은 문제를 조금씩 크게 만들어가는 것

 - 부분 문제들을 모아서 큰 문제를 하나 만들어가는 것을 반복하며 큰 문제를 해결

   ex) 위의 피보나치 수를 구하는 알고리즘은 Bottom-Up 방식의 예이다.

 

두 방법에 시간 차이가 존재하는가? -> 단정지을 수 없다.

재귀를 사용하는 Top-Down이 더 오래걸릴것이라고 느낄 수 있다.

(재귀마다 변수들을 생성하고, 스택오버플로우 문제 발생 가능)

그러나 Bottom-Up 방식은 무조건 존재하는 모든 부분 문제들을 풀어야 큰 문제를 풀 수 있다는 단점을 가진다.

결국 어떤 방식이 시간이 더 적게 소요된다고 단정지을 수 없다.

 

다만 파이썬은 Bottom-Up을 추천하고

스택오버플로우 문제가 상대적으로 잘 발생하지 않는 C나 JAVA는 Top-Down을 추천한다. 

 

# 다이나믹 프로그래밍 문제 풀이는 점화식을 정의하는 것으로부터 시작한다.