- geeksforgeeks: Greedy Algorithms
- 각 단계에서 지역 최적해를 찾음으로써 최종적으로 전역 최적해를 구하는 방법
- 완벽한 전역 최적해를 도출한다는 보장은 없으나 그 근사치를 얻을 수 있다.
- 최적화 문제를 빠르고 효율적으로 해결할 수 있다.
- 탐욕적 선택 속성 (Greedy Choice Property):
이전 선택이 이후의 선택에 영향을 주지 않아야 한다.
따라서 각 단계의 정보나 선택에 의존성이 있는 문제(재귀적 확인이 필요한 문제)에 적용될 수 없다. - 최적 부분 구조 (Optimal Substructure):
문제를 부분 문제로 나누었을 때, 각 부분 문제의 최적해를 결합하면 전체 문제의 최적해를 구할 수 있어야 한다.
- 문제에서 주어진 리소스를 정렬
- 최종 결과를 담을 변수 선언
- 선택 절차(Selection Procedure): 각 단계에서 지역 최적해를 선택
- 적절성 검사(Feasibility Check): 선택이 문제의 조건을 만족하는지 검사 후 최종 결과에 반영
- 해답 검사(Solution Check): 전체 문제가 해결되었는지 검사 후 그렇지 않으면 선택 절차로 돌아가 과정을 반복