동적 계획법(DP, Dynamic Programming) 과 메모이제이션(Memoization)

DP와 메모이제이션 개념

동적 계획법 (dp) - 복잡한 문제를 작은 부분 문제(subproblem)으로 쪼개어, 각 부분 문제의 최적해를 계산하여 중복 계산을 피하면서 전체 문제의 최적해를 찾는 알고리즘 설계 기법. 전체 문제의 하위 부분 문제의 답으로부터 전체의 답을 구하는 방법.

 

메모이제이션 - 중복 계산을 피하기 위해 계산 결과를 따로 저장해놓는 기법. dp 에서 사용되는 기법 중 하나이다. dp에 포함되는 개념.

 

 

DP의 2가지 주요 요소

1. Optimal Substructure (최적 부분 구조) : 하위 문제의 최적해로부터 전체 문제의 최적해를 구할 수 있음.

2. Overlapping sub-problems (겹치는 부분 문제) : 동일한 부분문제가 여러번 반복적으로 해결되는 현상. 메모이제이션을 사용하여 계산 결과를 저장하여 활용.

 

DP는 2가지 방법으로 해결 가능

1. Top-down : 재귀를 사용하는 방식.

큰 문제 해결하기 위해 재귀 함수 호출 -> 작은 부분 문제들 해결하기 위해 자기 자신 호출 -> 이 과정에서 중복 계산 피하기 위해 테이블에 저장.

 

2. Bottom-up : 작은 부분 문제부터 시작하여 상향식으로 문제 해결.

작은 부분 문제 해결하기 위해 반복문 -> 작은 부분 문제들의 최적해를 계산하고, 그 결과 저장. -> 이전에 계산한 작은 부분문제들의 최적해로 점진적으로 큰 문제 해결 -> 전체 문제 최적해 구함.

 

Top-down으로 해결 가능하면 반드시 Bottom-up으로 해결이 가능할까?

 => 반드시 가능. 반복문이냐 재귀냐의 차이만 있다.

 

분할 정복과 DP의 차이

분할 정복은 동일한 부분 문제를 여러번 사용하지는 않음. 즉 Overlapping sub-problems의 요소가 없음.