[자료구조] 그리디 알고리즘과 다이나믹 프로그래밍

🎞️ 그리디 알고리즘

탐욕법

• 현재 상황에서 지금 당장 좋은것만 고르는 방법
• 현재의 선택이 나중에 미칠 영향은 고려하지 않음
• 최적의 답이 보장되지 않음

용도

• 애초에 완벽한 답이 필요 없을 때
• 그리디 알고리즘이 최적의 답을 보장해줄 때

🎞️ 동적 계획법

Dynamic Programming

• 하나의 큰 문제를 여러 개의 작은 문제로 나눠 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용
• 모든 상황을 고려하여 최적의 경로 구함

용도

• 이전의 선택이 미래에 영향을 줄 때
• 모든 경우의 수를 원할 때

🎞️ 그리디 알고리즘 vs. 동적 계획법

• 시간
  • 그리디 알고리즘: 빠름
  • 동적 계획법: 느림
• 최적 방법
  • 그리디 알고리즘: 전체적인 상황에서는 최적이 아닐수도 있음
  • 동적 계획법: 전체 상황에서도 최적임

---

참고:

• [알고리즘] 그리디(Greedy) 알고리즘과 예제 (파이썬)