[알고리즘] 그리디 알고리즘(Greedy Algorithm)

📌  그리디 알고리즘이란?

그리디 알고리즘(탐욕 알고리즘)은 문제를 해결하는 과정에서 현재 상황에서 가장 최선이라고 생각되는 선택을 반복적으로 하여 최적의 해를 구하려고 하는 알고리즘이다.  즉, "지금 가장 좋아 보이는 것을 선택하는 것이 최종적으로도 가장 좋은 선택!" 이라는 가정을 기반으로 동작한다. 하지만 항상 최적의 해를 보장하지는 않는다! 그리디 알고리즘이 성공하려면 특정한 조건들이 충족되어야 한다. 😅

 

🔍 그리디 알고리즘의 주요 특징

1️⃣ 지역 최적해(Local Optimal Solution)

• 현재 단계에서 가장 최선의 선택을 반복적으로 선택
• 이 선택이 전역 최적해(Global Optimal Solution)가 될 것이라고 가정

2️⃣ 단순하고 빠른 해결 방법

• 복잡한 계산 대신 현재 상태에서 최선의 선택을 반복하기 때문에 구현이 단순하고 빠름

3️⃣ 탐욕적 선택 속성

• 매 단계의 선택이 전체 문제를 해결하는 데 영향을 미치지 않거나, 긍정적인 영향을 준다

 

🔧그리디 알고리즘의 활용

• 최소 비용 문제: 최단 경로 찾기(다익스트라 알고리즘 ), 최소 스패닝 트리(Kruskal, Prim 알고리즘)
• 스케줄링 문제: 회의실 배정 문제, 작업 스케줄링 문제
• 거스름돈 문제: 가장 적은 동전으로 거스름돈을 줄 때

 

🚫 그리디 알고리즘 사용 시 주의할 점

 

• 그리디 알고리즘은 항상 최적해를 보장하지는 않는다. 😥
  ➡️ 모든 경우에 대해 최적의 결과를 보장하려면 탐욕적 선택 속성과 최적 부분 구조를 만족해야 함
• 문제를 풀기 전에 그리디 알고리즘을 사용할 수 있는 조건인지 확인하는 것이 중요함
• 최적해를 보장하지 못하는 경우, 다른 알고리즘(동적 계획법, 완전 탐색 등)을 사용해야 할 수 있음

 

 

🥐 그리디 알고리즘 과정

1️⃣ 해 선택:

• 현재 상태에서 가장 최선이라고 생각되는 해를 고름

2️⃣ 적절성 검사:

• 선택한 해가 문제의 제약 조건을 만족하는지 확인
• 조건에 맞지 않으면 선택을 변경하거나 다른 해를 고름

3️⃣ 해 검사:

• 지금까지 선택한 해가 전체 문제를 해결할 수 있는지 검사
• 만약 문제를 해결하지 못했다면 다시 1️⃣로 돌아가 새로운 해를 선택

 

💡 그리디 알고리즘 동작 방식 예제

 

거스름돈 문제

💰 문제: 손님에게 거스름돈으로 동전을 가장 적게 줄 수 있는 방법을 찾아라.
🔢 조건: 동전 단위는 500원, 100원, 50원, 10원. (무제한 사용 가능)

 

1️⃣ 가장 큰 단위 동전(500원)부터 사용.

• 1260 ÷ 500 = 2개 사용 → 남은 금액: 260원

2️⃣ 그다음 큰 단위 동전(100원) 사용.

• 260 ÷ 100 = 2개 사용 → 남은 금액: 60원

3️⃣ 50원 동전 사용.

• 60 ÷ 50 = 1개 사용 → 남은 금액: 10원

4️⃣ 10원 동전 사용.

• 10 ÷ 10 = 1개 사용 → 남은 금액: 0원

결과: 최소 동전 개수는 6개! 🎉

 

 

✅ 다음 게시글에서 예제 문제로 더 자세히 이해해보도록 하겠습니다!

[JAVA][Baekjoon] 11047번 동전 0

[JAVA][Baekjoon] 1744번 수 묶기 🌟🌟🌟

[JAVA][Baekjoon] 1931번 회의실 배정 🌟🌟🌟

[JAVA][Baekjoon] 1541번 잃어버린 괄호 🌟🌟🌟