동적 계획법(Dynamic Programming)이 그리디(Greedy) 알고리즘과 어떻게 다른지 설명하고, 두 알고리즘이 각각 어떤 문제 유형에 주로 적용되는지 구체적인 예시를 들어주세요.

동적 계획법과 그리디 알고리즘은 둘 다 최적화 문제를 해결하는 방법이지만, 접근 방식에 차이가 있습니다. 동적 계획법은 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 피합니다. 즉, "최적 부분 구조"와 "중복 부분 문제"라는 특징을 가집니다. 예를 들어, 피보나치 수열이나 최단 경로 문제를 풀 때 유용합니다.

반면, 그리디 알고리즘은 각 단계에서 "탐욕적 선택 속성"을 만족하는, 즉 당장 눈앞에 보이는 최적의 선택을 합니다. 하지만 이 지역적인 최적해가 항상 전역적인 최적해를 보장하지는 않습니다. 대표적인 예시로, 거스름돈 문제를 해결할 때 가장 큰 단위의 동전부터 사용하는 방법이 있습니다.

따라서, 문제의 특성에 따라 적절한 알고리즘을 선택해야 합니다. 동적 계획법은 최적해를 보장하지만, 계산 비용이 높을 수 있고, 그리디 알고리즘은 빠르지만 최적해를 보장하지 못할 수 있습니다.