Leta Learns

1. 동적계획법 : 큰 문제를 여러 개의 작은 부분으로 분할하여 해결하는 기법. 2. DP vs. Divide & Conquer Dynamic Programming Divide & Conquer 공통점 큰 문제를 여러 개의 작은 문제로 나눠서 해결한다. 차이점 작은 문제에서 중복 O 작은 문제에서 중복 X 3. DP의 조건 1) 작은(부분) 문제들이 중복된다. -> 부분 문제 한 번만 계산한 후 그 해를 테이블에 저장. -> 그 부분 문제가 중복될 때마다 테이블에서 미리 저장해둔 해를 반환. 2) 최적 부분 구조를 가진다. -> 작은 문제의 해로부터 큰 문제의 해를 구할 수 있음. 4. How To Solve DP Top-Down / 재귀함수를 사용하는 방식 (Memoization) -> 시간복잡도 문제..