Greedy

그리디 알고리즘

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

그리디 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

문제 해결

1. 선택: 현재 상태에서의 최적의 해답을 선택한다.

2. 적절성: 선택된 해가 문제의 조건을 만족하는지 검사한다.

3. 해답: 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

조건

그리디 알고리즘이 잘 적용되는 문제는 탐욕스러운 선택 조건과 최적 부분 구조 조건이라는 두가지 조건이 만족된다.

• 탐욕스러운 선택 조건: 앞의 선택이 이후의 선택에 영향을 주지 않는다.

• 최적 부분 구조 조건: 문제에 대한 최적해가 부분문제에 대해서도 최적해이다.