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

그리디 알고리즘

• 매 순간에 가장 최선의 선택을 해 답을 구하는 알고리즘
• 조건: 매 순간에서의 최선의 선택 = 문제에서의 최적해
• 접근 방식에 가까운 알고리즘임

 

그리디 알고리즘 사용 불가능한 경우 ❌

• 매 순간에서의 최선의 선택 ≠ 문제의 최적해
  → 수학적으로 접근하거나 DP(시간복잡도가 𝚶❨𝚴❩임)를 이용

 

실제 문제에서 그리디 알고리즘

• 매 순간에서의 최선의 선택 = 문제의 최적해 를 만족하는지 판단할 것
• 때에 따라, 위의 조건이 만족하도록 문제를 재해석 하는 능력도 필요
• 만약, 재해석을 해도 그리디를 적용할 수 없다면 다른 풀이를 떠올려야 함(브루트포스 or DP or 수학)
  
  
• Tip! 정렬과 그리디는 함께 사용되는 경우가 많음