다이나믹 프로그래밍 (Dynamic Programming) 기본 개념 최적화 문제를 해결하는 알고리즘 기술이다. 전체 문제의 최적 해가 부분 문제의 최적 해를 포함함을 활용한다. 이전에 계산한 값을 저장함으로써 동일 계산의 반복을 제거한다. 재귀적 구조 - 큰 문제 안에 닮음꼴의 작은 문제가 들어있는 구조다. - 관계중심으로 문제를 간명하게 파악 가능하다. 재귀적 해법 - 잘 쓰면 보약, 잘못 쓰면 맹독이다. - 심각한 중복 호출이 일어나는 경우가 있다. > 재귀적 해법이 바람직한 예 - 퀵 정렬, 병합 정렬 등의 정렬 알고리즘 - 계승(factorial) 구하기 - 그래프의 DFS > 재귀적 해법이 치명적인 예 - 피보나치수 구하기 - 행렬곱셈 최적순서 구하기 대표 문제 : 피보나치 수 아주 간단한 문..