Greedy(탐욕법)

Greedy

각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘

• 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론
• 이때, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 ‘근사한 값’을 목표로 함
• 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적 해를 구한 뒤 이를 결합하여 전체 문제의 최적 해를 구하는 경우에 주로 사용

 

속성

1. 탐욕 선택 속성
   • 각 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적 해를 구할 수 있는 경우
   • 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것
2. 최적 부분 구조
   • 전체 문제의 최적 해가 부분 문제의 최적 해로 구성될 수 있는 경우
   • 즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적 해를 구하는 것을 의미

 

단계

1. 문제의 최적 해 구조를 결정
2. 문제의 구조에 맞게 선택 절차를 정의
   • 선택 절차(Selection Procedure)
     • 이 단계에서는 ‘현재 상태’에서 ‘최적인 선택’을 함. 이 선택은 이후에는 바뀌지 않음.
3. 선택 절차에 따라 선택을 수행
4. 선택된 해가 문제의 조건을 만족하는지 검사
   • 적절성 검사(Feasibility Check)
     •  이 단계에서는 ‘현재 상태’에서 ‘최적인 선택’을 함. 이 선택은 이후에는 바뀌지 않음.
5. 조건을 만족하지 않으면 해당 해를 제외
6. 모든 선택이 완료되면 해답을 검사
   • 해답 검사(Solution Check)
     • 이 단계에서는 모든 선택이 완료되면, ‘최종 선택’이 ‘문제의 조건을 만족’하는지 확인. 조건을 만족하면 해답으로 인정
7. 조건을 만족하지 않으면 해답으로 인정되지 않음.

 

예시

💡 문제 확인

• 거스름돈으로 1260원을 거슬러줘야 할 때 500원, 100원, 50원, 10원 짜리 동전이 무한정 존재한다면, 가장 큰 동전부터 가능한 많이 사용하는 방식으로 거스름돈을 계산

💡 그리디 알고리즘 적용

1. 선택 절차 : 거스름돈 문제에서 가장 가치가 큰 동전부터 선택
2. 적절성 검사: 만약 선택된 동전의 가치가 거스름돈보다 크다면 다음으로 작은 동전을 선택
3. 해답 검사 : 합이 일치하면 거스름돈 문제가 해결