DP (동적 프로그래밍, Dynamic Programming)

1. 소개동적 프로그래밍이란? 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산를 방지하는 최적화 기법입니다. 언제 사용할까?DP는 다음과 같은 경우에 사용된다. 부분 문제가 반복적으로 등장하는 경우 최적 부분 구조 (Optimal Substructure): 부분 문제의 최적해를 이용해 전체 문제를 해결할 수 있을 때예를 들어, 피보나치 수열을 재귀로 구현하면 동일한 값이 여러 번 중복 계산된다.DP를 사용하면 이를 방지할 수 있다. 분할 정복과의 차이점 동적 프로그래밍분할 정복부분 문제 중복 여부OX대표 예제피보나치 수열, 배낭 문제, LCS병합 정렬, 퀵 정렬해결 방식저장하여 재사용독립적인 작은 문제로 나눠 ..