Dynamic Programming (동적 계획법) - 큰 문제를 작은 문제로 나누어 결과를 저장하여 다시 큰 문제를 해결하는 방법 (기억하며 풀기!)

DP를 사용하는 이유 - 일반적인 재귀를 사용하면 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다!

DP를 사용할 때

1. 최적 부분 구조 (Optimal Substructure)

• 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결 할 수 있는 경우

2. 중복되는 부분 문제 (Overlapping Subproblem)

• 동일한 작은 문제를 반복적으로 해결해야 하는 경우
• BUT 부분 문제가 중복되지 않는 경우에는 사용할 수 없음

대표적인 DP 문제 - 피보나치 수열

• 피보나치 수열을 재귀함수로도 구현할 수 있음!

  

• BUT 피보나치 수열을 단순 재귀함수로 구현하게 되면 n이 커질수록 수행 시간이 기하급수적으로 늘어남

  

• DP 방법 중 한 종류

• 한 번 구한 결과를 메모리 공간에 메모한 후 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법

  

• 색칠된 노드만 방문하면 됨!

DP 문제를 푸는 방법 - 탑다운(Top-Down) vs 바텀업(Bottom-Up)

1. 탑다운(Top-Down) : 하향식

• 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식

2. 바텀업(Bottom-Up) : 상향식

• 가장 작은 문제들부터 답을 구해가면서 전체 문제의 답을 찾는 방식
• 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있음

• 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 이어서 큰 문제를 해결한다는 점은 같음
• 하위 문제가 중복이 일어나지 않음 - 분할 정복
• 하위 문제가 중복이 일어남 - 동적 프로그래밍