그리디?!
Greedy(그리디)는 욕생쟁이라고 하는 별칭이 있습니다.
특정 조건만 맞으면 지금 당장의 상황을 선택하는 방법입니다. 더 좋은 방법이 있는지, 더 효율적인 방법이 있는지를 확인하는 그런 상황이 아닌, 지금 단계만 집중하는 것입니다.
이렇게 욕심하는 방법을 근시안적이라고 하는 부르기도 하더군요!
장점
- 진행하는 단계의 현재만 고려하기 때문에, 다시 돌아가는 등이 타 알고리즘의 구조들이 생략되게 됩니다. 즉, 계산 속도가 매우 빠릅니다.
- 그리디 유형 문제들에서는 효율적으로 최적의 해를 찾을 수 있다는 것이 가장 좋은 점이죠.
단점
- 현재의 단계에서의 최적해를 고려하기에, 이게 전체를 고려했을 때 최적해일 것이라는 보장은 할 수가 없습니다. 즉, 결과를 도출했지만 그것이 해당 문제의 최적해가 아닐 수도 있다는 것이죠.
설계 절차
- 선정 과정(selection procedure) : 현재 상태에서 가장 좋으리라고 생각되는 해답모음(solution set)에 포함시킨다.
- 적정성점검(feasibility check) : 새로 얻은 해답모음이 적절한지를 결정한다.
- 해답점검(solution check) : 새로 얻은 해답모음이 최적의 해인지를 결정한다.
그리디 문제를 푸는 과정보단 그리디 문제를 직접 설계할 때의 고려사항입니다. 과제나 알고리즘 문제 출제에 있어서 최종 제출 전 검토할 수 있는 내용인 것 같습니다.
문제 풀이 기준
- 탐욕적 선택 조건 : 한 번의 선택이 다음 선택과는 전혀 무관해야 합니다. 현재 선택했다고 해서 다음 부분해에 영향을 준다면 탐욕적으로 할 수 없습니다.
- 최적 부분 구조 : 선택에 있어서 매 순간의 최적해여야 합니다. 그리고 이렇게 얻은 결과가 이 문제에 대한 최적이여야 합니다.
위가 해결할 수 없다면 그리디로 해결할 수 없는 문제니 다른 방법을 고려해야 합니다.
적용 문제
아래 문제는 그리디의 두 조건을 보장하는 유형입니다.
- 다익스트라(Dijkstra) 알고리즘 : 최단 경로 문제
- 허프만 코딩 알고리즘 : 압축 알고리즘으로 허프만 트리를 진행할 때
참고링크
✍🏻 뭐든 배우면 다 자산이 되겠죠!