그리디 알고리즘

• 최적화 문제를 해결하는 알고리즘
  • 최적화(optimization) 문제: 가능한 해들 중에서 가장 좋은 해를 찾는 법
• 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림
• 그리디 알고리즘은 데이터 간의 관계를 고려하지 않고 수행 과정에서 '욕심내어' 최소값 또는 최대 값을 가진 데이터를 선택
  • 근시안적 선택

  1. 그리디 알고리즘의 수행 과정

• 그리디 알고리즘은 근시안적인 선택으로 부분적인 최적해를 찾고, 이들을 모아서(축적하여) 문제의 최적해를 얻음
  

2. 그리디 알고리즘의 특징

• 그리디 알고리즘은 일단 한 번 선택하면, 이를 절대로 번복하지 않음
  • 즉, 선택한 데이터를 버리고 다른 것을 취하지 않음
• 이러한 특성 때문에 대부분의 그리디 알고리즘은 단순하며, 주로 제한적인 문제만이 그리디 알고리즘으로 해결 가능함
• 그리디 알고리즘은 문제와 상황에 따라 최적의 답을 찾을 수도, 못찾을 수도 있다.