[Algorithm] Greedy

[Algorithm] 거품 정렬

매 선택에서 지금 이 순간 당장 최적인 답을 선택해 적합한 결과를 도출하는 알고리즘이다.

특정 조건에서만 사용이 가능하다.

해당 조건을 만족하는 문제를 매트로이드 문제라고 한다.

---

개요

• 설명
• 조건
• 특징
• 단계

---

설명

• 매 선택을 지역적으로 최선인 것을 선택해 최적의 답을 찾아가는 알고리즘.
• 지역적으로 최선의 답이 전역적으로 최선이 아닐 수 있다.
• 따라서, 이하 두 조건을 만족해야 사용할 수 있다.
  • Greedy Choice Property(탐욕스러운 선택 조건)
  • Optimal Substructure(최적 부분 구조 조건)

---

조건

Greedy Choice Property

• 각 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우.
• 즉, 지금의 선택이 이후의 선택에 영향을 주어선 안된다.

  Optiaml Substructure

• 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우.
• 즉, 전체 문제를 부분 문제로 나누어 최적해를 구한 다음 이를 조합했을 때 전체 문제의 최적해가 돼야 한다.

---

특징

• 전체 상황에서 최적의 결과를 보장하지 못한다.
• 빠르다!
• 최적의 답안은 아니지만 최적에 근사한 답안을 제시하므로 근사 알고리즘에 속한다.

---

단계

1. 문제의 최적해 구조 결정
2. 문제 구조에 맞게 선택 절차 정의 (Selection Procedure, 선택 절차)
3. 선택 절차에 맞게 선택 수행
4. 선택된 해가 문제 조건을 만족하는지 검사 (Feasiblitiy Check, 적절성 검사)
5. 조건을 만족하지 않으면 해당 해 제외
6. 모든 선택이 완료되면 해답을 검사 (Solution Check, 해답 검사)
7. 조건을 만족하지 않으면 다시 검사

Selection Procedure

• 현재 상태

  에서 최적인 선택을 한다. 이 선택은 바뀌지 않는다.

Feasibility Check

• 선택한 것이 문제의 조건을 만족하는지 확인한다.
  • 만족하지 않으면 제외한다.

Solution Check

• 모든 선택이 완료되면 최종 선택이 문제의 조건을 만족하는지 확인한다.
  • 조건을 만족하면 해답으로 인정한다.

---