그리디 알고리즘

그리디 알고리즘(Greedy Algorithm)

부분의 최적해가 합쳐져서 전체의 최적해를 이룬다

최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.

• 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 한다.

• 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.

특징

1. 탐욕적 선택 속성
   그리디 알고리즘은 각 단계에서 지금 당장 가장 최적인 선택을 한다. 이 선택이 나중에 문제의 최적 해가 되도록 하는 특성을 갖고 있다.

2. 최적 부분 구조
   문제의 최적 해가 부분 문제에 대한 최적 해들로 구성되어 있다. 즉, 문제를 작은 부분 문제로 쪼개어 각 부분 문제에 대한 최적 해를 구할 수 있다.

3. 시간 복잡도가 낮음
   그리디 알고리즘은 일반적으로 각 단계에서 간단한 계산만 필요로 하기 때문에 시간 복잡도가 낮을 수 있다. 따라서 많은 경우에 효율적인 해결 방법으로 사용될 수 있다.