그리디 알고리즘

• 그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라 하는데 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 기법이다.

• 그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다.

  • 로컬 최적의 선택을 하면 글로벌 최적에 도달할 수 있다고 믿는다.

• 각 단계에서 최선의 선택을 한 것이 전체적으로 봤을 때도 최선이라 생각하고 문제를 푸는 알고리즘이다. 그러므로 최종 정답을 구했을 때 그것이 최선이라는 보장은 없다.

• 그리디는 대부분 최적화 문제를 대상으로 한다. 합리적인 시간 내에 최적에 가까운 답을 찾을 수 있다는 점에서 매우 유용한 알고리즘이기도 하다.

  • 최적화 문제 : 여러 개의 해답 중에서 주어진 조건을 만족하는 최적의 해답을 찾는 문제, 최적의 기준은 문제에 따라 다르며 보통 특정 기준에 맞는 최댓값 또는 최솟값을 사용한다.

• 그리디 알고리즘의 문제 해결 방법

  • 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
  • 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
  • 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

• 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.

  • 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  • 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

• 하지만 이 조건들이 만족하지 않더라도 그리디 알고리즘은 정답을 근사하게 찾는 용도로 활용할 수 있으며 대부분의 경우 계산 속도가 빠르므로 매우 실용적이다.

• 그리디 알고리즘의 대표적인 예로는 동전 거스름돈 문제가 있다.

  • 500원 100원 50원 10원 짜리 동전이 있을 때 동전 갯수를 최소화한 거스름돈을 구할 때 500원 짜리를 최대한 거슬러주고 100원 짜리를 최대한 거슬러주고 50원 10원 단계별로 최선의 선택을 하면 최적의 해가 나온다.

• 3주차 숙제

  • https://github.com/alswp006/IT_skill_up/tree/main/민제/3주차/숙제