그리디 알고리즘

눈앞의 이익만 추구하는 알고리즘

do{
    가장 좋아보이는 선택을 한다;
} until(해 구성 완료)

그리디 알고리즘은 최종 해답에 도달하기까지, 각 단계에서 최적이라고 생각되는, 가장 좋아보이는 선택을 반복하는 알고리즘이다.

그리디 알고리즘 특징

• 지역적으로 최적인 해가, 전역적으로 최적인 해라는 보장은 없다.
• 각 단계의 선택이 다음 단계의 선택에 영향을 끼치지 않는다.

근사 알고리즘

그리디 알고리즘은 최적해를 보장하지 않는다. 하지만 지역적으로는 최적해를 매번 선택한다는 점에서 최적해에 근접한 값을 구할 수 있다.

PS에서의 그리디

최적해가 보장되지 않는 예

• 이진트리의 최적합 경로 찾기

  모든 노드를 다 탐색하지 않으면 최적해를 찾을 수 없음.

• 보따리 문제 (부피가 M인 보따리에 부피가 Wi , 가치가 Pi인물건 최대한 많이 넣기)
  
• 거스름돈 문제

  동전 액면이 작은 단위의 배수가 아닌 경우 최적해를 찾을 수 없음.

최적해가 보장되는 예

• 최소 신장 트리(MST)
• 회의실 시간 분배 문제
  등