[목차]

점화식이란?

먼저 점화식이라고 하는 것은 어떤 수열(규칙이 있는 수들의 모임)의 일반항을 그 이전의 항들을 이용하여 정의한 식을 뜻합니다.

다이나믹 프로그래밍

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함

• 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 바텀업)으로 구성

  • 탑다운 (하향식)
  • 바텀업 (상향식)

• 다이나믹 프로그래밍은 동적 계획법이라고도 불림

• 일반적인 프로그래밍 분야에서 동적(Dynamic)의 의미

  • 자료구조에서 **동적 할당(Dynamic Allocation)**은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미함
  • 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어

다이나믹 프로그래밍의 조건

문제가 다음의 조건을 만족할 때 사용 가능

1. 최적 부분 구조 (Optimal Substructure)
   1. 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음