TABLE OF CONTENTS
그리디 알고리즘이란?
그리디 알고리즘 or 탐욕 알고리즘
최적의 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘
→ 따라서, 항상 최적의 값을 보장하는 것이 아니라, 최적의 값의 ‘근사한 값’을 목표로 한다!
그리디 알고리즘의 특징
- 순간마다 하는 선택들은, 그 순간에 대해 지역적으로 최적
- 선택들을 계속 수집하여 전역적인 해답을 만들었다고 해서, 그것이 최적은 아님
→ 하지만, 그리디 알고리즘 적용 가능한 문제들은, 지역적으로 최적이면서 전역적으로 최적인 문제들
그리디 알고리즘 주요 속성
다음 두 가지 조건이 성립해야, 그리디 알고리즘을 적용할 수 있다.
탐욕 선택 속성 (Greedy Choice Property)
각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우
→ 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져오게 됨.
최적 부분 구조 (Optimal Substructure)
전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’될 수 있는 경우
→ 즉, 각 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후, 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미.
그리디 알고리즘의 단계
순서 | 절차 | 비고 |
1 | 문제의 최적해 구조를 결정합니다. | ㅤ |
2 | 문제의 구조에 맞게 선택 절차를 정의합니다. | 선택 절차(Selection Procedure) → ‘현재 상태’에서 ‘최적인 선택’을 합니다. 이 선택은 이후에는 바뀌지 않습니다. |
3 | 선택 절차에 따라 선택을 수행합니다. | ㅤ |
4 | 선택된 해가 문제의 조건을 만족하는지 검사합니다. | 적절성 검사(Feasibility Check) → 선택한 항목이 ‘문제의 조건’을 만족시키는지 확인합니다. 조건을 만족시키지 않으면 해당 항목은 제외됩니다. |
5 | 조건을 만족하지 않으면 해당 해를 제외합니다. | ㅤ |
6 | 모든 선택이 완료되면 해답을 검사합니다. | 해답 검사(Solution Check) → 모든 선택이 완료되면, ‘최종 선택’이 ‘문제의 조건을 만족’시키는지 확인합니다. 조건을 만족시키면 해답으로 인정됩니다. |
7 | 조건을 만족하지 않으면 해답으로 인정되지 않습니다. | ㅤ |
Made with Bullet