[C++] 알튜비튜 6주차 - 그리디 알고리즘

그리디

• 욕심쟁이 방법 탐욕적 방법, 탐욕 알고리즘 등으로 불린다.
• 우리가 원하는 답을 여러개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어간다.
• 모든 단계의 선택지를 고려해보지는 않는다.
• 각 단계마다 지금 당장 좋은 근시안적 방법을 선택한다.
• 계산속도가 빠르다.
• -> 많은 경우 최적해를 찾지 못한다. 특정 조건 하에서만 적용가능

사용조건

• 시간적, 공간적 제약으로 최적해를 구하지 못해, 근사해를 구해야 하는 문제 (대개 출제 x)
• 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제
  • 탐욕선택속성 : 탐욕적으로 선택하더라도 문제의 최적해가 보장될 때(손해 x)
  • 최적 부분 구조 : 부분 문제의 최적해가 전체 문제의 최적해로 확장될 수 있을 때
    • 알고리즘의 정당성을 증명하는 과정 연습