그리디 알고리즘(Greedy Algorithm, 탐욕법)

1. 그리디 알고리즘이란?

• 최적의 값을 구해야 하는 상황에서 전체적인 상황을 상정하여 구하는 것이 아닌, 각 단계에서 최선의 선택을 하는 근시안적 방법론입니다.
• 전체적인 상황을 상정하지 않기 때문에 항상 최적의 해를 구하는 것이 보장되어있지 않지만, 근사해를 구하는것이 가능합니다.

아래와 같은 트리에서 각 노드의 합의 최대값을 구하는 상황일때, 탐욕법을 이용하면 각 단계에서 가장 큰 값을 선택하게 되어 5->10->4와 같이 선택하게 됩니다.

최적의 해는 5->7->9이므로 탐욕법을 이용하는것이 항상 최적의 해를 구하는 것은 아님을 보여줍니다.

출처 https://velog.io/@kyunghwan1207/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm-%ED%83%90%EC%9A%95%EB%B2%95

2. 그리디 알고리즘의 특징

2.1 그리디 알고리즘의 조건

그리디 알고리즘이 근사값이 아닌 최적값을 보장하는 조건 2가지가 있습니다.

 

• 탐욕 선택 속성 (Greedy Choice Property)

현재의 선택이 미래의 선택에 영향을 끼치지 않는다.

• 최적 부분 구조 (Optimal Substructure)

부분의 최적해가 모여 전체의 최적해가 된다.

 

문제가 이 두가지의 조건을 만족한다면 그리디 알고리즘을 사용해 최적값을 구할 수 있습니다.

2.2 그리디 알고리즘의 단계

1. 선택절차(Selection Procedure)

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

 

2. 적절성 검사(Feasibility Check)

선택한 항목이 문제의 조건을 만족시키는지 확인한다.

 

3. 해답 검사(Solution Check)

모든 선택이 완료되면, 최종 선택이 문제의 조건을 만족시키는지 확인한다.

 

Reference

https://adjh54.tistory.com/212