[알고리즘] 그리디(greedy)
✏️ 그리디 알고리즘 (Greedy Algorithm)
- 현재 시점에서 가장 좋은 답을 택하는 알고리즘
- 그리디 알고리즘으로 해법을 찾았을 때는 그 해법이 정당한지를 검토해야 한다.
- 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시한다.
주의할 점 : 그리디의 해답이 전체의 최적해를 보장하지는 않는다.
언제 사용할 수 있을까?
- 현재 선택이 미래 선택에 영향을 미치지 않는다.
- 부분의 최적해가 모이면 전체 최적해가 된다.
'어떻게 정렬해야 할까?' 에 대한 답을 찾아야 함 (정렬을 잘 해야 함)
