[알고리즘] 그리디 알고리즘

그리디 알고리즘

• 최적화 문제(Optimization Problem) 에서 최적해를 구하는데 사용되는 근시안적인 방법
  • 최적화 문제(Optimization Problem) : 가능한 해들 중에서 가장 좋은 해를 찾는 문제
• 탐욕적(Greedy) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
• 한번 선택된 것은 번복하지 않음
• 단, 최적해를 반드시 구한다는 보장이 없기 때문에 증명 과정이 필요함
  • 최적해를 반드시 구한다는 보장이 없다? ex) 동전 거스름돈 문제
    • 최소의 동전으로 800원을 만드는 경우
      • 동전 종류가 500, 100, 50, 10 일 경우 가능
      • 동전 종류가 500, 400, 100, 50, 10 일 경우 불가능

그리디 알고리즘의 조건

• 탐욕적 알고리즘 사용을 위해서는 아래 두 가지 속성을 만족함을 증명해야함
  • 탐욕적 선택 속성(greedy choice property)
    • 탐욕적으로만 선택해도 최적해를 구할 수 있음
  • 최적 부분 구조(optimal substructure property)
    • 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음