Greedy Algorithm

1. 그리디 알고리즘

탐욕 알고리즘 또는 탐욕적 알고리즘

• 매순간 최적이라고 생각되는 것(지역적 최적)을 선택하여 최적해에 도달하는 기법
  • 현재의 선택이 나중의 선택에 미칠 영향을 고려하지 않음
  • 즉, 전역적 최적해를 반드시 보장하지 않음
• 대부분의 경우 속도가 빠른 알고리즘이기 때문에, 최적에 근사한 값을 빠르게 구할 때도 사용함(근사 알고리즘)

반대로,

• 지역적 최적인 해를 찾으면서 궁극적으로 해결하고자 하는 문제의 조건을 만족시킴으로써 전역해를 찾도록 함

2. ✌️ 문제해결에 적용하기 위한 두 가지 조건

1. Greedy choice property

• 각 단계의 최적해를 선택했을 때 최적해에 도달할 수 있다.

2. Optimal substructure

• 문제의 최적해는 문제의 부분 문제를 해결하는 최적해를 포함한다.

3. Matroid

탐욕 알고리즘이 항상 최적해를 발견할 수 있는 특별한 구조의 문제

• 최적해를 구할 수 있는 모든 문제가 매트로이드 구조를 띄지는 않는다.
• 어떤 유한 집합 S의 부분 집합들의 집합인 I (즉, I ⊆ 2^S)가 아래 성질을 만족하면 집합 I는 Matroid이다.
  • Heredity (유전성)
    A∈I 이고, B⊆A 이면 B∈I
  • Augmentation (추가성)
    A,B ∈ I 이고, |A| < |B| 이면, A ∪ {x} ∈ I 인 x ∈ B−A가 존재
  • Exchange (교환성)
    A,B ∈ I 에 대해 어떠한 b ∈ B−A 이든, A ∪ {b}−{a} ∈ I가 되는 a ∈ A−B 가 존재한다.

참고

https://brilliant.org/wiki/greedy-algorithm/
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/
https://dad-rock.tistory.com/673
https://ko.wikipedia.org/wiki/%EB%A7%A4%ED%8A%B8%EB%A1%9C%EC%9D%B4%EB%93%9C