그리디

그리디(Greedy) 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘.

동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수.

하지만, 항상 최적의 해를 보장하지 못한다는 단점도 있음.

그리디 알고리즘을 사용하기 전에는 항상 그리디 알고리즘을 적용할 때의 논리 유무를 충분히 고려해야함.

 

그리디 알고리즘은 다음과 같은 3단계를 반복.

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

---

문제를 잘 읽고 푸는 것 말고는 그리디 알고리즘이라고 해서 특별히 적용해야하는 방식은 없는 것 같다.

그냥 이런 타입의 문제를 그리디하게? 풀 수 있다는 정도로 구분할 수 있는 것 같다.