그리디(Greedy) 알고리즘
그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다. 하지만 항상 최적의 해를 보장하지 못한다는 단점도 있다. 따라서 그리디 알고리즘을 적용할 때의 논리 유무를 충분히 살펴야 한다.
그리디 알고리즘의 핵심 이론
① 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
② 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
③ 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 ①로 돌아가 같은 과정을 반복한다.
