python 다이나믹 프로그래밍

[다이나믹프로그래밍] DP - JS, Python

다이나믹 프로그래밍 큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하려는 알고리즘 기법 다이나믹 프로그래밍을 사용할 수 있는 경우 1. 최적 부분 구조(큰 문제를 작은 문제로 나눌 수 있다) 2. 중복되는 부분 문제(동일한 작은 문제를 반복적으로 해결 (최적화)) 위의 두 조건이 모두 충족할 경우 다미나믹 프로그래밍을 사용할 수 있다 (점화식 사용) 다이나믹 프로그래밍 최적화의 핵심 각 작은 문제는 한 번만 풀어야 한다 Optimal Substructure를 만족하기 때문에 같은 문제는 구현 때마다 정답이 같다 정답을 한 번 구했으면 어딘가에 메모해 놓는다 메모하는 것을 코드에서는 배열로 구현할 수 있다 메모한다고 해서 memoization 용어를 쓴다 다이나믹 프로그래밍의 ..