그리디는 공식이나 방법론이 아닌 하나의 개념이라서 정리할 게 많지 않다

그리디

---

그리디는 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘으로 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다.

5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자.
이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다.

그리디 알고리즘은 최적의 해를 보장하는 경우도 많지만 보장하지 못하는 경우가 더 많다.

위의 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다.

그럴 때는 다이나믹 프로그래밍 등의 기타 알고리즘 기법을 적용해야 한다.

그리디 알고리즘은 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등으로 극단적으로 문제에 접근한다는 점에서 정렬기법이 함께 사용되는 경우가 많다.

• 탐욕 선택 속성
• 최적 부분 구조

위 특성을 가지는 문제들을 해결하는데있어 그리디는 강점을 가진다.

사용

---

대표적으로 그리디가 사용되는 곳은 다음과 같다.

• AI에 있어서 결정 트리 학습법(Decision Tree Learning)
• 활동 선택 문제(Activity selection problem)
• 거스름돈 문제
• 최소 신장 트리 (Minimum spanning tree)
• 제약조건이 많은 대부분의 문제
• 다익스트라 알고리즘
• 허프만 코드
• 크러스컬 알고리즘

백준 그리디 알고리즘 문제집에 들어가서 기본 그리디 문제를 풀어보고 감을 잡아보는 것이 좋겠다.