그리디 - 5. 그리디 알고리즘 vs 다른 알고리즘

📌 5. 그리디 알고리즘 vs 다른 알고리즘

✅ 학습 목표

이번 단원에서는 그리디 알고리즘과 다이나믹 프로그래밍(DP)의 차이점을 학습하고, 그리디 알고리즘이 항상 최적해를 보장하지 않는 경우를 이해합니다.

1. 그리디 알고리즘이 최적해를 항상 보장하지 않는다는 점 이해
2. 다이나믹 프로그래밍(DP)과 비교하여 어떤 경우 DP가 필요한지 학습
3. 그리디 알고리즘이 적용되지 않는 문제 유형을 파악하는 능력 기르기

---

✅ 학습 내용

1️⃣ 그리디 알고리즘 vs 다이나믹 프로그래밍(DP)

알고리즘	방식	장점	단점
그리디(Greedy)	현재 단계에서 가장 최선의 선택을 반복	빠르고 구현이 간단함	항상 최적해를 보장하지 않음
다이나믹 프로그래밍(DP)	모든 경우를 고려하여 최적의 해를 구함	최적해를 보장함	시간과 메모리 사용량이 큼

📌 핵심 차이점

• 그리디: 한 번 선택하면 되돌릴 수 없음 → 항상 최적해를 보장하지 않음
• DP: 모든 가능성을 계산하여 최적해를 구함 → 비용이 크지만 최적해를 보장함

---

2️⃣ 그리디 알고리즘이 적용되지 않는 경우

(1) 최대 증가 부분 수열 (LIS)

가장 긴 증가하는 부분 수열을 찾는 문제

문제 예시

입력: {10, 20, 10, 30, 20, 50}
출력: 4  (최대 증가 부분 수열: {10, 20, 30, 50})

✅ 이 문제는 DP로 풀어야 최적해를 보장할 수 있음!
그리디 방식으로는 항상 최선의 선택을 보장하지 못함.

---

(2) 최소 동전 개수 문제

특정한 동전 조합에서는 그리디가 오답을 낼 수 있음.

문제 예시

• 동전 종류: {1원, 3원, 4원}
• 목표 금액: 6원

📌 그리디 알고리즘 적용

1. 가장 큰 동전(4원) 선택 → 남은 금액 2원
2. 1원 동전 2개 선택 → 총 3개 사용
   ✅ 정답은 2개 (3원 + 3원)이지만, 그리디는 오답(3개) 발생

💡 최적해를 찾으려면 다이나믹 프로그래밍(DP) 방식이 필요!

---

✅ 정리

1. 그리디 알고리즘은 항상 최적해를 보장하지 않는다
2. DP는 모든 경우를 고려하여 최적해를 보장하지만, 계산 비용이 큼
3. 최대 증가 부분 수열(LIS), 특정 동전 거스름돈 문제 등은 그리디가 적합하지 않음
4. 그리디를 적용하기 전에 항상 문제 조건을 확인해야 한다!