목록최소 신장 트리 (1)

Dawn

[알고리즘] 그리디 알고리즘 (Greedy Algorithm, 탐욕법)

그리디 알고리즘 (Greedy Algorithm, 탐욕법) 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.매순간 좋아 보이는 것만 고르며, 현재 선택이 나중에 미칠 영향을 고려하지 않고, 상황이 오면 그때 적합한 것을 선택한다.알고리즘이 작성할 때 두 가지 조건을 만족시켜주어야 한다.탐욕스러운 선택 조건 (Greedy Choice Property)각 단계에서 최적의 선택을 함으로써 전체 문제의 최적 해를 얻어야 한다.현재 단계에서의 최적 선택이 이후 단계에서도 여전히 최적 선택으로 이어져야 하고, 이를 통해 한 번의 선택이 전체 문제 해결에 유리하게 작용하도록 구성해야 한다. 최적 부분 구조(Optimal Substructure)문제의 최적 해답이 그 하위 문제들의 최적 해답으로부터 구해질 수 있는..
알고리즘 2024. 7. 11. 02:06
이전 Prev 1 Next 다음