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

💡 그리디 알고리즘(탐욕법, Greedy Algorithm) 이란?

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

• 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있습니다.

• 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용됩니다.

💡 해당 경우에서는 그리디 알고리즘과 같은 형태로 노드를 선택하는 방식입니다.

💡 각각 상황에서 '최적'이라고 생각하는 방법을 선택합니다.(상황에서 가장 높은 수를 선택합니다.)

2) 그리디 알고리즘 주요 속성

1. 탐욕 선택 속성

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

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

2. 최적 부분 구조

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

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

3) 그리디 알고리즘 vs 동적 계획법

💡 비슷한 방법으로 해결이 되는 동적 계획법과 비교를 해봅니다.

더 자세히

설탕 배달 ATM 거스름돈