그리디(Greedy) 알고리즘

*나동빈님의 그리디 알고리즘 강의 및 강의자료를 참고해서 공부 한 내용입니다.

그리디(Greedy) 알고리즘

• 그리디 알고리즘은 '당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘'으로, 가장 단순한 형태의 알고리즘
• 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. 또한, '특정한 상황'에 있어서 그리디 알고리즘이 최적의 해를 보장할 수 있다.
• 대표적인 예제: 거스름 돈 문제
  거스름 돈을 줄 때, 가장 적은 양의 화폐를 주는 것이 제일 편하다. 만약 560원을 거슬러줘야한다면, 10원 56개를 주는 것 보다 50원 1개 + 50원 1개 + 10원 1개를 주는 것이 총 3개로 더 편하다.
  따라서, 이 경우 '무조건 더 큰 화폐 단위부터 거슬라 준다'는 알고리즘만 지키면 최적의 해를 보장할 수 있다.
• 위의 예시와 같이, 그리디 알고리즘은 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등으로 극단적으로 문제에 접근한다. 이러한 특징으로 인해, 정렬(sort)이 함께 사용되는 경우가 많다.
• 그리디가 최적의 해를 보장하는 경우도 많지만, 최적의 해를 보장하지 못하는 경우가 더 많다. 이 경우, Dynamic Programming등의 기타 알고리즘 기법을 적용해야 한다.