min's devlog min's devlog

다이나믹 프로그래밍 (Dynamic Programming) 어떤 문제를 공간을 더 사용하며 연산속도를 증가시키는 방법이다. 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 것이다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 • 동일한 작은 문제를 반복적으로 해결해야 한다 * 뒤로 돌릴 수 없을 때, 특정한 상태가 있을 때, 최적해를 구해야할 때 대표적 예시 : 피보나치 수열 an= an-1 + an-2, a1 = 1, a2 = 1 피보나치 수열을 재귀함수로 구현하면 다음과 같다. def fibo(x): if x == 1 or x == 2: ret..