동적 계획법에 대해 설명해보세요

---

동적 계획법의 작동 방식

• 동적 계획법이란 복잡하고 큰 문제를 간단하고 여러 개의 작은 문제로 나누어 푸는 방법을 말한다. 분할 정복과 비슷하나, 계산한 부분 문제 결과를 저장하여 필요할 때 다시 꺼내어 사용한다는 점에서 차이가 있다. 이 결과들을 재활용하는 메모이제이션(Memoization)기법으로 속도를 향상시킬 수 있다.

---

동적 계획법의 조건

• 동적 계획법을 사용하기 위해선 다음 조건들이 만족해야 한다.

  • 부분 반복 문제(Overlapping Subproblem)
    작은 문제가 반복적으로 발생하는 경우를 말한다. 반복적으로 나타나지 않는다면 결과를 재사용할 수 없기 때문이다.
  • 최적 부분 구조(Optibal Substructure)
    작은 부분 문제에서 구한 최적의 답을 통해 큰 문제의 최적의 답을 구할 수 있어야 한다. 즉 전체 문제의 최적의 답은 부분 문제의 최적의 답으로 구성된다.

---

동적 계획법의 접근 방법

• 동적 계획법을 사용할 때, 두 가지 접근 방법이 존재한다.

  • Bottom - Up
    아래(부분 문제)에서 위(전체 문제)로 접근하는 방법으로, 반복문을 이용하여 부분 문제부터 해결하여 점차 큰 문제를 해결해나가는 방법이다.
  • Top - Down
    위에서 아래로 접근하는 방법으로, 전체 문제를 부분 문제로 나누어가며 재귀 호출을 이용하여 해결하는 방법이다.

• Bottom - Up의 경우에는 구현이 쉽지만 소스의 가독성이 떨어질 수 있고, Top - Down의 경우에는 소스의 가독성이 증가되지만 구현이 어려울 수 있다.

---

결론

동적 계획법은 전체 문제를 부분 문제로 나누어 푸는 방법입니다. 이 때, 부분 문제의 최적해를 큰 문제의 최적해를 구할 때 반복적으로 사용하는 메모이제이션 기법을 통해 문제를 해결하는 속도를 향상시킵니다. 동적 계획법을 사용하기 위한 두 가지 조건이 있는데, 하나는 작은 문제가 반복적으로 발생하는 부분 반복 문제여야 하며, 다른 하나는 전체 문제의 최적의 해가 부분 문제의 최적의 해인 최적 부분 구조여야 합니다. 접근 방법으로는 반복문을 활용한 Bottom-up 방법과, 재귀 호출을 활용한 Top-Down 방법이 있습니다.