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

그리디 알고리즘? 

최적해를 구하는 데 사용되는 알고리즘의 한 유형으로 문제를 해결하는 과정에서 현재 상황에서 가장 좋다고 생각되는 선택을 반복적으로 하는 방식이다.

즉 전체적인 최적해를 고려하지 않고 현재 단계에서 가장 좋은 선택을 하는 것을 반복하여 최종적인 해결책을 찾는 알고리즘이다.

이 알고리즘은 각 단계에서의 최적 선택이 결국 전체 문제에 대한 최적 해결책을 보장할 수 있을 때 유효하다.

 

 

특징

• 탐욕적 선택 속성 (Greedy Choice Property): 각 단계에서 현 시점에서 가장 최적인 선택을 한다.
• 최적 부분 구조 (Optimal Substructure): 문제의 최적 해결 방법이 부분 문제들의 최적 해결 방법으로 구성될 수 있다.
• 장점
  • 간단하고 직관적: 구현이 간단하고 이해하기 쉬운 편
  • 빠른 수행 속도: 일반적으로 다른 알고리즘에 비해 계산 속도가 빠름
• 단점
  • 최적해 보장 X: 항상 최적해를 보장하지 않기 때문에 문제에 따라 최적해를 구하지 못할 수도 있음
  • 문제 특화: 특정 문제에서만 유효하며 모든 문제에 적용하지 못함

 

그리디 알고리즘을 많이 사용하는 예제 

1. 동전 거스름돈 문제 
   
   • 문제: 주어진 동전 단위로 특정 금액을 최소 개수의 동전으로 만들기
   • 접근: 가장 큰 단위의 동전부터 가능한 많이 사용
2. 활동 선택 문제
   • 문제: 최대한 많은 활동을 선택하기 위해 각 활동의 시작 시간과 종료 시간이 주어졌을 때 겹치지 않게 최대한 많은 활동을 선택하는 문제
   • 접근: 종료 시간이 가장 빠른 활동을 먼저 선택
3. 배낭 문제
   • 문제: 각 아이템의 일부를 배낭에 넣을 수 있는 경우 각 물건의 무게와 가치를 고려하여 배낭에 넣을 수 있는 최대 가치를 구하는 문제 (단, 물건을 쪼갤 수 있음)
   • 접근: 가치 대 무게 비율이 높은 물건을 먼저 선택