다이나믹 프로그래밍(Dynamic Programming)

 다이나믹 프로그래밍(동적 계획법) 이란?

다이나믹 프로그래밍은 재귀에 대한 최적화이다.

이말은 중복된 부분에 대한 문제가 있다면, 이에 대한 결과를 저장해둔다. 그리고 동일한 부분에서의 문제가 다시 발생한다면, 이 결과를 재사용하는 방법이다.

 

이런 사례는 피보나치 수열에서 쉽게 찾아볼 수 있다.

피보나치 수열의 점화식은 다음과 같다. 

f(n) = f(n - 1) + f(n - 2)

이때 n = 4라고 한다면,

f(4) = f(3) + f(2)

를 구해야 하는데, 이때 전에 구해두었던 f(3) 과 f(2)의 값을 다시 구하지 않고 저장해두었다가 다시 사용하는 것을 의미한다.

---

특징

• 커다란 문제를 나누어 해결하는 편이다.
• 앞서 말했듯이, 이전에 풀었던 문제와 동일한 문제일 경우, 다시 연산 하는 것이 아니라 이전의 결과를 사용한다.
• 인접한 항들 간의 관계를 통해 점화식을 이용한다.
• 시간과 공간면에서 효율적이다.

---

점화식

• 인접한 항들 간의 관계식
• 동적 계획법 문제를 풀 때는, 점화식을 세우고 문제를 해결하면 효율적으로 해결할 수 있다.

ex) 피보나치 문제 점화식 = f(n) = f(n - 1) + f(n - 2)

---

다이나믹 프로그래밍에서의 Top-Down 방식과 Bottom-Up 방식

DP(다이나믹 프로그래밍)은 원래 Bottom-Up 방식이지만, Top-Down 방식도 사용할 수 있다.

 

Top-Down

• 위에서 아래로 순차적으로 문제를 해결하는 방식
• 재귀함수를 사용하여 문제를 해결

Bottom-Up

• 아래서 위로 순차적으로 문제를 해결하는 방식
• 반목문을 사용하여 문제를 해결

---

연관 문제

문제 - 1 페이지