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

알고리즘 풀이를 하다보면 많은 문제가 다이나믹 프로그래밍(DP)를 이용해 풀이가 가능합니다.

그렇기 때문에 알고리즘을 공부하기 위해서는 꼭 알아가야 하는 파트입니다.

다이나믹 프로그래밍은 동적 계획법으로도 불리는데, 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어지면 각 단계의 부분 문제에 대한 답을 기반으로 하여 전체 문제의 답을 구하는 방법 입니다. 

정리하자면 큰 문제를 작은 문제들로 쪼개어 푸는 알고리즘이라 생각하면 됩니다.

TMI - 다이나믹 프로그래밍의 이름은 알고리즘의 고안자인 리차드 벨만이 Dynamic이란 말이 멋있어서 붙였다고 합니다.

문제를 다이나믹 프로그래밍을 사용하여 풀기 위해서는 2가지 속성을 만족해야합니다.

1. Overlapping Subproblem (부분 문제 반복)
2. Optimal Substructure (최적부분 구조)

---

Overlapping Subproblem

Overlapping Subproblem으로는 피보나치 수열이 대표적인 예시인데요.

피보나치수 (0, 1, 1, 2, 3, 5, 8, 13, 21 ...) $F_{0} = 0$  $F_{1} = 1$ $F_{n} = F_{n-1}+F_{n-2}(n>=2)$

위처럼 피보나치는 큰 문제인 $F_{n}$을 구하기 위해 $F_{n-1}, F_{n-2}$ 각각의 작은 문제 두개로 나누어 풀어야 하기 때문입니다.

큰 문제 : N번째 피보나치 수를 구하는 문제 작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

큰 문제 : N-1번째 피보나치 수를 구하는 문제 작은 문제 : N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제

큰 문제 : N-2번째 피보나치 수를 구하는 문제 작은 문제 : N-3번째 피보나치 수를 구하는 문제, N-4번째 피보나치 수를 구하는 문제

이렇게 큰 문제와 작은 문제를 같은 방법으로 풀 수 있고, 문제를 작은 문제로 쪼갤 수 있을때

Overlapping Subproblem(겹치는 부분 문제)라고 합니다.

---

Optimal Substructure

Optimal Substructure는 문제의 정답을 사용해 작은 문제의 정답을 구할 수 있습니다.

예시로 서울에서 부산으로 가는  가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면,

대전에서 부산을 가는 가장 빠른길은 대구를 거쳐야 하는 것 입니다.

서울 -> 대전 -> 대구 -> 부산 대전 -> 대구 -> 부산

이런식으로 같은 문제를 구할 때 마다 정답이 같은 예시로는 위에서 사용한 피보나치 수열이 있는데요.

4번째 피보나치 수열의 값은 12번째, 10번째, 8번째 .. 5번째 피보나치 수를 구하면서 항상 변함없이 같은 값을 가지게 됩니다.

---

Memoization(메모이제이션)

다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 하고, Optimal Substructure를 만족하기 때문에 같은 문제를 구할 때 마다 정답이 같습니다.

피보나치 수열을 예시로 들면 1, 1, 2, 3, 5, 8, 13...의 수를 이루는데 이를 위에서 본 다음 값 =  바로 전 값 + 전전 값  이라는 점화식을 가지게 되는데 재귀함수를 사용하여 풀게되면 간단하게 풀이가 가능하지만 수열의 길이가 증가함에 따라 호출되는 함수의 수가 기하급수적으로 증가하기 때문에 다항 시간을 벗어나 지수 시간 시간복잡도가 발생하여 일정 길이 이상의 순열을 구하기가 힘듭니다.

피보나치 수열을 구하기 위해 호출되는 함수를 보면 겹치는 부분을 찾을 수 있다.

매번 문제의 부분문제 정답을 구하는 것은 효율성이 떨어지기 때문에, 정해진 정답을 어딘가에 메모하는 방법이 메모이제이션입니다.

메모이제이션을 사용하게 되면 한번 계산을 마친 값은 다시 계산할 필요가 없으므로 f(n)을 구하는데 O(N)의 시간만이 필요로 합니다.

그렇기 때문에 긴 길이의 가진 피보나치 수열또한 O(N)의 시간 복잡도로 풀이가 가능해집니다.

allocate array for memo, setting all entries to zero;
initialize memo[1] and memo[2] to 1;

fib(n) {
   if memo[n] is zero:
       memo[n] = fib(n-1) + fib(n-2);
   return memo[n];
}

다이나믹 프로그래밍 문제를 풀게 되면 보통 배열을 사용하여 저장합니다.

---

Top-down & Bottom-up

다이나믹 프로그래밍의 구현 방식은 두가지가 존재합니다.

재귀를 사용하는 Top-down과 반복문을 사용하는 Bottom-up이 있습니다.

이 둘의 시간차이는 편하게 이야기하자면 알수 없음입니다.

다만 재귀로 풀이를 하면 스택오버플로우가 발생할 수 있기 때문에 신경을 써줘야 합니다.

특히 Python환경에서 Top-down으로 풀이를 하게된다면 스택오버플로우에 유의해야 합니다.