그리디 알고리즘_GreedyAlgorithm

그리디 알고리즘(Greedy Algorithm)

• 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론
• 각 단계에서 최적이라고 생각되는것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 이다.
• 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 ‘근시값’을 목표로 하고 있다.

그리디 알고리즘 주요속성

1. 탐욕선택속성(Greedy Choice Property)
   1. 각 단계에서 ‘최선의 선택’을 했을때 전체 문제에 대한 최적해를 구할 수 있는 경우
2. 최적부분구조(Optimal Substructure)
   1. 전체 문제의 최적해가 부분 문제의 최적해로 구성 될 수 있는 경우
   2. 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 다음 이를 조합해 전체 문제의 최적해를 구하는 것을 의미

단계

1. 문제의 최적해 구조를 결정한다
2. 문제의 구조에 맞게 선택절차를 정의한다. - 선택절차
3. 선택절차에 따라 선택수행
4. 선택된 해가 문제의 조건을 만족하는지 검사한다. - 적절성검사
5. 조건을 만족하지 않으면 해당 해를 제외한다.
6. 모든 선택이 완료되면 해답을 검사한다 - 해답검사
7. 조건을 만족하지 않으면 해답으로 인정되지 않는다.

• 선택절차 (Selection precedure) : 현재상태에서 최적인 선택을 한다
• 적절성 검사(Feasibility check) : 선택한 항목이 문제의 조건을 만족하는지 확인한다
• 해답검사(Solution check) : 모든 선택이 완료, 최종선택이 문제의 조건을 만족 시키는지 확인한다.