그리디 (Greedy) 알고리즘

• 그리디(Greedy) 알고리즘은 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘
• 대표적으로 거스름돈 문제가 있는데, 단순하게 큰 경우 부터 찾는 알고리즘과 같이 간단하게 탐욕적으로 문제를 해결하는 기법
• 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등으로 극단적으로 문제를 접근한다는 점에서 정렬 기법이 함께 사용되는 경우가 많음.
• 최적해에 가까운 값을 구하기 위해 사용
  • 그리디를 통해 구한 결과값이 항상 최적해인게 아님
• 여러 경우 중 하나를 결정할 때마다, 매순간 최적이라 생각하는 경우를 선택하여 최종 결과값을 구함
• 반드시 최적해가 보장되는 것이 아니기 때문에 근사치 추정에 활용