[알고리즘] [19] 동적 계획법

1. 메모이제이션 (Memoization)

• 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장하여 다시 계산하지 않도록 하는 기술
• 동적 계획법의 핵심이다.
• 추가적인 메모리 공간이 필요하다.

2. 동적 계획법 적용 요건

• 중복 부분 문제 구조 : 동일한 부분 문제들로 구성되어 있는가?
• 최적 부분 문제 구조 : 최적을 구하는 문제인가?

중복 부분 문제 구조

• DP는 큰 문제를 이루는 작은 문제를 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결한다.
• 순환적 관계를 명시하기 위해 주로 점화식을 사용한다.
• 이전에 계산된 작은 문제의 해가 다음 문제에서 필요하게 되므로(Overlapping subproblems) 이전의 작은 문제의 해들을 저장 공간에 저장한다.
• 이전의 해 얻기 위해 table을 참조하여 중복된 계산을 피한다.

최적 부분 문제 구조

• 최적화의 원칙을 만족해야 동적 계획법을 효율적으로 적용할 수 있다.
• 큰 문제의 최적해가 작은 문제들의 최적 해로 구성되지 않는다면 동적 계획법을 적용할 수 없다.