그리디 vs 동적 프로그래밍 비교 (Greedy vs DP)

그리디 vs 동적 프로그래밍 비교 (Greedy vs DP)

최적화 문제를 해결하는 두 가지 주요 패러다임으로, 그리디는 매 단계 지역 최적 선택, DP는 부분 문제의 최적해를 결합하여 전역 최적 도출

목적: 최적화 문제 해결 전략 선택, 알고리즘 설계 가이드

그리디 (Greedy)

• •원리: 각 단계에서 현재 가장 좋아 보이는 선택 (지역 최적)
• •조건: 그리디 선택 속성 + 최적 부분 구조
• •특징: 한 번의 선택 후 되돌아가지 않음, 빠름
• •시간: 일반적으로 O(n) 또는 O(n log n)
• •예시: 거스름돈(특정 화폐), 활동 선택, 크루스칼, 프림, 허프만

동적 프로그래밍 (DP)

• •원리: 부분 문제의 최적해 저장(메모이제이션), 결합
• •조건: 최적 부분 구조 + 중복 부분 문제
• •특징: 모든 가능성 고려, 항상 최적해 보장
• •시간: O(n²) 또는 O(n×m) 등 다항식
• •예시: 배낭 문제, LCS, LIS, 행렬 곱셈, 플로이드-워셜

선택 기준

• •그리디 선택 속성 증명 가능 → 그리디 (더 효율적)
• •부분 문제가 중복 → DP
• •지역 최적 ≠ 전역 최적 → DP 필요

그리디 실패 예시: 거스름돈(1, 3, 4원으로 6원 → 그리디: 4+1+1, 최적: 3+3)

장점/단점

• •그리디: 빠름/최적 보장 안 됨
• •DP: 최적 보장/느림, 메모리 사용

비교: 그리디(지역최적/빠름) vs DP(전역최적/느림) vs 완전탐색(모든경우)

연관: 최적화 문제, 배낭 문제, 최단 경로, 그래프 알고리즘