1. 그리디 알고리즘 (Greedy Algorithmm)

각각의 상황에서 최적이라고 생각하는 방법을 선택하는 알고리즘

최적의 값을 구하기 위해 사용되는 방법론으로, 각 단계에서 최적이라고 생각되는 것을 선택 (휴리스틱 접근법) 해나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘입니다.

장점

• 빠르고 실용적인 솔루션이 필요한 실시간 환경에서 실용적입니다.
• 최적의 해를 찾기 쉽지 않을 때에도 빠르고 실용적인 해를 제공합니다.

단점

• 각 단계에서 지역적으로 최적의 솔루션을 찾기 때문에 항상 전역적으로 최적의 솔루션을 얻는 것은 아닙니다.

2. 적용 조건

1. 탐욕 선택 속성 (Greedy Choice Property)

   각 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우

2. 최적 부분 구조 (Optimal Substructure)

   전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우

3. 적용 단계

1. 최적해 구조 결정
2. 구조에 맞는 선택 절차(Selection Procedure) 정의

• 선택 절차: 현재 상태에서 최적인 선택을 하며, 이후에 바뀌지 않습니다.

3. 절차에 따라 선택 수행
4. 선택된 해의 적절성 검사(Feasibility Check)

• 적절성 검사: 선택한 항목이 문제의 조건을 만족하는지 확인합니다.

5. 조건을 만족하지 않는 해 제외
6. 선택 완료시 해답 검사(Solution Check)

• 해답 검사: 최종 선택이 문제의 조건을 만족하는지 확인합니다.

조건을 만족하지 않는 경우 해답으로 인정되지 않습니다.

사진 출처: What is Greedy algorithms