[알고리즘] DP (0) - DP 문제를 해결하는 방법

 

 

 

 

🧐 Memoization

재귀적으로 반복되는 어떠한 함수의 중간 결과를 저장하는 기법을 의미합니다.

 

 

 

 

 

 

 

 

🧐 Dynamic Programming

Recursion(재귀)과 Memoization을 사용하여 문제를 해결하는 기법을 의미합니다.

DP의 본질은 재귀를 올바르고 똑똑하게 하는 것이므로, 재귀를 위한 Recurrence Relation을 올바르게 세우는 것이 중요합니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 DP 문제 해결 순서

1. 문제를 정확하게 정의합니다.

2. 정의된 문제에 대하여 부분 문제(Subproblem)을 정의합니다.

3. Subproblem을 이용하여 Recurrence Relation을 세웁니다.

4. Memoization을 이용하여 Recurrence Relation을 계산합니다.

    - 중간 결과물들들 저장할 자료구조를 설정하여야 합니다. 보통은 n차원 배열을 사용합니다.

    - Subproblem들 간의 Dependency를 확인합니다. 예를 들어 F(n) = F(n-1) + F(n-2)라면 F(n)은 F(n-1)과 F(n-2)에 의존합니다.

    - Dependency에 기반아혀 Subproblem들의 답을 구하는 순서를 정해야 합니다.

5. 시간 복잡도를 분석하고 알고리즘을 실제 코드로 작성합니다.