그리디 알고리즘이란 ?

• 각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘
• 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 근사한 값을 목표로 한다. ⇒ 근사 알고리즘
• 주로, 문제를 분할 가능한 문제들로 분할한 뒤 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용한다.

그리디 알고리즘 주요 속성

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

1. 탐욕 선택 속성

• 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다.

1. 최적 부분 구조

• 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미한다.

그리디 알고리즘 단계

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다.
   • 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

예제 문제 : 거스름돈

1. 해 선택 : 가장 가치가 큰 동전부터 선택을 한다.