[알고리즘] 탐욕 알고리즘

그리디 알고리즘이란?

• 최적해를 구하는데 사용되는 알고리즘 중 하나.
• 각 단계에서 가장 최선의 선택을 하는 알고리즘으로, 현재 상태에서 최선의 선택을 해가면서 최종적으로 전체 문제의 최적해를 구하는 것.
• 문제에 따라서는 최적해를 구하지 못할 수도 있음(근사적인 방법)

그리디 알고리즘을 해결하는 방법

1. 문제를 이해하고 정의
   • 문제의 입력, 출력, 제약 조건 등을 파악합니다.
2. 문제의 최적화 대상을 정의
   • 문제의 최적화 대상이 무엇인지 명확히 이해하고 정의합니다.
3. 가능한 모든 해를 나열
   • 가능한 모든 해를 나열합니다.
4. 가능한 모든 해 중에서 최적해를 찾을 수 있는 그리디 선택 조건을 찾음
   • 문제의 최적화 대상과 관련하여 그리디 선택 조건을 찾습니다.
   • 그리디 선택 조건은 각 단계에서 가장 최선의 선택을 하는 조건입니다.
5. 그리디 선택 조건을 적용
   • 각 단계에서 그리디 선택 조건에 따라 최선의 선택을 합니다.
6. 선택된 해를 부분해 집합에 추가
   • 선택된 해를 부분해 집합에 추가합니다.
7. 부분해 집합이 최종해인지 확인
   • 모든 입력에 대해 최종해를 보장하는지 확인합니다.

그리디 알고리즘의 성립 조건

• 최적 부분 구조(Optimal Substructure) : 문제의 최적해가 부분 문제의 최적해를 포함하는 성질입니다. 따라서, 부분 문제의 최적해를 찾고 이를 이용하여 전체 문제의 최적해를 찾을 수 있습니다.
• 탐욕 선택 속성(Greedy Choice Property) : 각 단계에서 그리디 선택 조건을 만족하면서 전체 문제의 최적해를 구할 수 있는 성질입니다. 이를 통해 각 단계에서 가장 최선의 선택을 계속해서 하면서 최종적으로 전체 문제의 최적해를 구할 수 있습니다.

그리디 알고리즘 문제의 예시

• 거스름돈 문제 : 가장 큰 화폐 단위부터 거슬러 줄 수 있는 돈을 최소한으로 거슬러 주는 문제
• 부분 배낭 문제 : 물건의 일부만 넣을 수 있는 배낭에 물건을 최대한으로 넣는 문제

[참고]
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/