1. 다이나믹 프로그래밍 (Dynamic Programming) - 분할정복법처럼 작은 문제들로 나누어 각각 해답을 찾고 원래 문제의 해답을 계산하는 방식 1) 메모이제이션 (Memoization) 을 이용한 DP - Top Down 방식이다. - 반복되는 결과를 메모리에 저장해서 중복 호출 되었을 때 한번 더 계산하지 않고, 메모리에 저장된 값을 가져와서 사용 - 가장 큰 문제를 방문 후 작은 문제를 호출하여 답을 찾는 방식 2) 반복문을 이용한 DP - Bottom Up 방식이다. - 재귀가 필요없다. (시간과 메모리 사용량을 줄일 수 있다.) - for 문을 이용해서 수행한다. - 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식