[알고리즘] 동적 프로그래밍 (DP) 란? feat.동적 계획법

동적 프로그래밍(Dynamic programming) 란? 동적 프로그래밍은 "큰 문제"를 "부분 문제"로 나누고, "부분 문제"의 정답으로 "큰 문제"의 답을 찾는 알고리즘 설계 기법입니다. 동적 프로그래밍의 대표적인 예로 피보나치 수열을 예로 들 수 있는데요, 이 점화식을 코드로 표현하면 다음과 같습니다. F[1] = 1 F[2] = 1 F[1] = F[2] F[i] = F[i-1] + F[i-2] 점화식은 재귀식이라고도 하며 위 코드를 보면 피보나치 수열은 재귀적인 관계를 가지고 있다는 것을 알 수 있습니다. DP를 적용하기 위한 2가지 조건 동적 프로그래밍을 적용시키기 위해선 다음 고같은 두 가지가 만족되어야 합니다. 부분 반복 문제(Overlapping Subproblem) 최적 부분 구조(Op..