매트로이드란? 탐욕 알고리즘이 최적 해를 가려낼 수 있는 경우인지를 판별할 수 있게 하며, 독립성이라는 성질을 만족하는 수학적 공간 단, Greedy한 방법을 적용할 수 있는 모든 경우를 판별해낼 수 있는 것은 아니라서, 어떤 문제의 공간이 매트로이드 구조를 이루면, 탐욕 알고리즘이 최적해를 도출해낼 수 있지만, 탐욕 알고리즘이 최적해를 도출할 수 있는 모든 문제가 매트로이드 구조를 띄는 것은 아니다. 탐욕 알고리즘은 꼭 최적해가 아니여도 최적해에 근사한 값을 찾아낼 수 있다는 점에서 유용한 알고리즘이다. 💡 어떤 유한 집합 n의 부분 집합들의 집합인 𝐼(즉, 𝐼⊆ 2ⁿ)가 아래 성질을 만족하면 집합 𝐼는 Matroid이다. 매트로이드의 특성 상속성(Heredity) A∈I이고, B⊆A이면 B∈I이다. ..
