[TIL] 탐욕 알고리즘 : Greedy

🤲🏻 탐욕 알고리즘 Greedy

  - 매 선택에서 현재 당장 최적의 답을 선택하여 최적의 결과 도출

▪️  탐욕 알고리즘 문제 해결 과정

    ① 선택 절차

    - 현재 상태에서의 최적의 해답을 선택

    ② 적절성 검사

    - 선택된 해가 문제의 조건을 만족하는지 검사

    ③ 해답 검사

    - 원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택절차로 돌아가 반복

---

▪️  탐욕 알고리즘 적용 조건

  ① 탐욕 선택 속성

     - 항상 안전하다는 것이 보장되어야 함 

     - 이전의 선택이 이후에 영향을 주지 않음

  ② 최적 부분 구조

     - 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야 함

---

💡 객체 정렬 기준 구현

  ① Comparable

    - compareTo()를 오버라이딩해서 구현

    - 일반적으로 정렬할 객체는 implements로 Comparable 인터페이스를 추가하여 구현

  ② Comparator

    - compare()를 오버라이딩해서 구현

    - 일반적으로 별도 클래스를 정의해서 구현 ( 동일한 객체에 다양한 정렬 기준을 가진 클래스 작성 가능 )