반응형 [PCCP] 알고리즘 - 그리디 1. 이론- Greedy: - 지역 최적해를 구함. 전역 최적해 장담 불가. - 해결과정에서 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택을 번복하지 않음- 그리디 알고리즘 최적해 보장 조건 - Optimal Substructure(최적 부분 구조): 부분해 과정이 최적해 과정과 일치 - Greedy Selection Property(그리디 선택 속성): 선택과정이 다른 과정에 영향을 주지 않음- Spanning Tree 1) 모든 정점이 간선으로 연결 2) 간선의 개수는 (정점의 개수 - 1)과 동일- Minimum Spanning Tree(최소신장트리) 1) 모든 정점이 간선으로 연결 2) 간선의 개수는 (정점의 개수 - 1)과 동일 3) 간선.. 2024. 12. 15. 이전 1 다음 반응형
