⚙동적 프로그래밍(DP: Dynamic Programming)

여기서 프로그래밍은 "테이블을 만든다" 는 뜻이라고 한다. 그리고 다이나믹..하지도 않다.
그래서 어떤 서울대 교수님은 기억하기 프로그래밍이라는 용어를 쓰기도 한다고 한다.

우선, 동적 프로그래밍은 어떠한 큰 문제를 작은 문제로 나누어 푸는 방법을 일컫는 풀이방법이다.
밑에서 더 자세히 살펴보기로 하자.

---

[1] 대략적인 풀이 흐름

1. Divide and Conquer(분할정복)과 비슷하지만 차이가 있다.

분할정복과의 결정적인 차이점은 바로 작은 문제가 중복이 일어나는지 안 일어나는지 여부이다.

• 분할정복: 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법.
  근데 이 작은 문제에서 반복되는 부분은 없음!
• 동적프로그래밍: 작은 부분문제들이 반복되는 것(답도 바뀌지 않음)을 이용하여 풀어나가는 방법.

2. Dynamic Programming의 조건

• 작은 문제가 반복이 일어나는 경우
• 같은 문제는 구할 때마다 정답이 같다.

3. Memoization(메모이제이션)

'동적 프로그래밍'에서는 작은 문제들이 반복되고, 이 작은 문제들의 결과값이 항상 같다! 따라서, 이 점을 이용하여 한 번 계산했던 작은 문제의 답을 저장해놓고, 동일한 문제가 발생했을 때 이 결과값을 다시 사용하여 중복 계산을 줄일 수 있게 된다. 이를 Memoization이라고 한다.

피보나치 수열 문제 풀이를 예로 들 수 있다. 아래와 같이 코드를 짜자.

int fiboData[100]; int fibo(int n) { fiboData[0] = 0; fiboData[1] = 1; if(n<=1) { return fiboData[n]; } else { for(int i=2; i<=n; i++) { fiboData[i] = fiboData[i-1] + fiboData[i-2]; } return fiboData[n]; } }

fiboData라는 배열을 생성한다. 이 배열에는 연산한 값들이 저장될 것이다. n이 1 이하일 경우 0 또는 1을 반환하고, n이 2 이상인 경우 fiboData배열을 n까지 연산하여 업데이트 시켜준 다음, fiboData[n]을 반환한다. 이렇게 되면 중복적인 계산이 줄어들게 된다.

---

[2] Bottom-Up 과 Top-Down 방식

Bottom-Up은 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식이며,
Top-Down은 가장 큰 문제를 방문한 후 작은 문제들을 호출하여 답을 찾는 방식이다.

흔히 Top-Down은 재귀 호출을, Bottom-Up은 반복문을 이용하여 구현한다.

1. Bottom-Up 방식

Bottom-Up 방식은 보통 반복문을 활용하여 해결한다. 위의 피보나치 코드가 Bottom-Up 방식이다.
즉, 문제풀이가 아래에서 위로 진행된다. (fiboData를 0부터 n까지 차근차근 구해나감)

2. Top-Down 방식

큰 문제를 풀 때, 작은 문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결한다. 즉, 문제풀이가 위에서 아래로 진행된다. 아래의 피보나치 코드를 보고 느낌을 이해하면 되겠다. (fiboData를 n부터 0까지 구해나감. 필요한 데이터가 없다면 그때가서야 구해서 쓴다.)

int fiboData[100]; fiboData[0] = 0; fiboData[1] = 1; int fibo(int n) { if(n<=1) return fiboData[n]; else return fibo(n-1) + fibo(n-2); }

3. Top-Down이 좋은가, Bottom-Up이 좋은가?

이 질문에는 정답이 없다고 한다.
Top-Down의 경우에는 소스코드의 가독성이 증가한다는 장점이 있지만 작성하기 조금 어렵다는 단점이 있고, Bottom-Up의 경우에는 풀기는 쉽지만 소스의 가독성이 저하될 수도 있다.

나는 백준 문제를 풀 때에는 Bottom-Up으로 풀면 통과하지만, Top-Down으로 풀면 재귀가 너무 많이 돌아가서 시간초과가 뜨는 경우를 많이 보긴 했다.

4. 동적 프로그래밍: 규칙이 있다!

동적 프로그래밍으로 풀 수 있는 문제에는 점화식이라던가(ex. 피보나치는
$a_0=0, a_1=1, a_n = a_{n-1} + a_{n-2} (n >= 2)$) 세울 수 있는 규칙 또는 식이 존재한다.
이 규칙을 잘 찾아서 이전에 구해놓은 작은 문제들인 dp[0], dp[1], dp[2], dp[3] 등을 이용해 풀어나가면 된다. 혹은 이것들을 이용해 점화식을 도출해낼 수도 있다.