[Algorithm] Greedy Algorithm

Greedy Algorithm이란?

• greedy : 탐욕스러운, 욕심 많은
• 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘입니다.
• 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있습니다.
• 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용됩니다.

주요 속성

💡 문제를 풀 때 두 가지 조건이 성립해야 그리디 알고리즘을 적용할 수 있습니다.

1. 탐욕 선택 속성(Greedy Choice Property)
2. 최적 부분 구조(Optimal Substructure)

💡 탐욕 선택 속성(Greedy Choice Property) 이란?

• 각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말합니다. 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것입니다.

💡 최적 부분 구조(Optimal Substructure) 란?

• 전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’될 수 있는 경우를 말합니다. 즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미합니다.

Greedy Algorithm의 단계

💡 그리디 알고리즘의 단계

1. 문제의 최적해 구조를 결정합니다.

2. 문제의 구조에 맞게 선택 절차를 정의합니다 : 선택 절차(Selection Procedure)

3. 선택 절차에 따라 선택을 수행합니다.

4. 선택된 해가 문제의 조건을 만족하는지 검사합니다 : 적절성 검사(Feasibility Check)

5. 조건을 만족하지 않으면 해당 해를 제외합니다.

6. 모든 선택이 완료되면 해답을 검사합니다 : 해답 검사(Solution Check)

7. 조건을 만족하지 않으면 해답으로 인정되지 않습니다.

*중복 부분 문제는 해결하지 못함