Greed

• 전체가 아닌 현재 상태에서 최선의 선택을 하는 알고리즘
  • 전체 탐색보다 빠르지만 반드시 최적의 해를 도출하지는 않는다
  • 현재의 선택이 나중에 미칠 영향 고려 X
    
    
• 사전에 알고리즘을 외우고 있지 않아도 풀 수 있을 가능성이 높은 유형의 문제들
  • 정렬, 최단 경로 등의 알고리즘 유형은 알고리즘을 정확히 알고 있어야만 해결 가능하다
    
    
• 탐욕법 사용할지 안할지 판단이 중요
  • 각 부분에서의 선택이 다른 부분에게 영향을 주지 않는 경우
  • 서로간 배수인 경우에 탐욕법 적용 가능

     ex) 
      거스름돈, 최적의 해와 greed의 답이 같은 경우(서로간 배수)에 사용 가능하다는 것
      - 400원, 200원 : 서로 영향 X
        - 400원은 200원 2개로 총 400원, 결과적으로 같은 경우 
      - 만약 300원, 200원인 경우 서로 배수관계가 아니기 때문에 앞의 선택(300원)이 뒤에 선택(200원)에 영향 줌, 적용 X
        - 300원을 선택하고 안하고가 200원의 선택 갯수에 대해 영향을 준다

  • 동적계획법과 Greed 두 개의 알고리즘도 경계가 모호한 경우