• 현재 순간의 최적해를 선택하는 알고리즘
    • 탐욕 선택 속성 : 앞의 선택이 이후의 선택에 영향을 끼치지 않는다
    • 최적 부분 구조 : 각 순간의 최적해는 문제 전체의 최적해에 포함
  • 최적해를 찾지 못한다면 근사해를 구할 수도 있다
  • 속도가 빠르고 실용적이다
  • 정렬과 관련이 있다
    • 일반적으로 그리디 알고리즘은 정렬을 하고 차례로 선택해 나간다
  • 각 순간의 최대값이나 최소값을 출력하는 우선순위큐 자료구조가 그리디에 많이 사용된다

Greedy vs DP

  1. 공통점 : 최적 부분 구조를 갖는다
  2. 차이점
    • Greedy : 각 단계마다 로컬 최적해를 찾으며 좁혀나가 글로벌 최적해를 구하는 접근 (Top-Down)
    • DP : 하위 문제의 최적해를 찾은 다음 결합하여 글로벌 최적해를 구하는 접근 (Bottom-Up)

문제

  1. 동전 거스름돈(동전의 액면이 배수 관계일 경우)
    • ex) 우리나라처럼 500, 100, 50, 10원 (10x5=50 / 50x2=100 / 100x5=500)
  2. Fractional 배낭 문제(짐을 쪼갤 수 있는 경우)
  3. 최단 경로
    1. 플로이드 알고리즘
    2. 다익스트라 알고리즘
  4. 집합 커버링