다이나믹 프로그래밍 알고리즘이란?

문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다.

다이나믹 프로그래밍 vs 그리디 알고리즘

그리디 알고리즘은 항상 그 순간에 최적이라고 생각되는 것을 선택하면서 풀이

다이나믹 알고리즘은 “중복된 하위 문제들”의 결과를 저장해뒀다가 풀이

알고리즘과 풀이 가능한 문제들의 특징

• 중복된 하위 문제들 | * 0-1 배낭 문제
• 피보나치 수열
• 다익스트라 알고리즘 | | 그리디 알고리즘 | * 최적 부분 구조
• 탐욕 선택 속성 | * 분할 가능 배낭 문제
• 다익스트라 알고리즘 | | 분할 정복 | * 최적 부분 구조 | * 병합 정렬
• 퀵 정렬 |

최적 부분 구조

서울에서 부산까지 가는 최단 경로 ⇒ (서울→대구) + (대구→부산)

이와 같이 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성됨. 이러한 구조를 최적 부분 구조라한다. 이는 분할 정복으로 풀이 가능. 또한 다이나믹 프로그래밍과 그리디 알고리즘으로도 접근해볼 수 있다.