큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 일반적으로 재귀 함수보다 반복문을 사용하는 방식이 더 성능이 좋음 시간 복잡도 : O(N)

사용조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

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

큰 문제를 해결하기 위해 작은 문제를 호출

• 재귀 함수 이용하는 방식

1) 메모이제이션(Memoization) 기법

= 캐싱(Caching)

한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 가져오는 기법

• 한 번 구한 정보 리스트에 저장
• 배열 활용

💡문제 해결 과정

1. 점화식 작성
2. 재귀 방식으로 풀어보기(반복)
3. 동적 계획법으로 재귀 + 메모이제이션으로 구현

2. 보텀업(Bottom-Up) 방식 - 상향식

작은 문제부터 차근차근 답을 도출

• 반복문을 이용하는 방식