Dynamic Programming 동적계획법

큰 문제를 작은 문제로 나누어 풀고, 작은 문제의 해답을 저장하여 재활용함으로써 중복 계산을 줄이고 효율성을 높이는 알고리즘 설계 기법

 

1. 탑다운 (Top-Down):

• 재귀와 메모이제이션을 사용하여 문제를 풀어나감
• 큰 문제를 먼저 풀기 시작하고, 하위 문제를 재귀적으로 호출하여 해결
• 이미 계산된 하위 문제의 결과를 메모이제이션(dp)으로 저장하고 재사용

2. 바텀업 (Bottom-Up):

• 반복문을 사용하여 작은 문제부터 시작해서 큰 문제를 해결
• 기본값부터 차례로 계산하며, 작은 문제의 결과를 기반으로 큰 문제를 해결