그리디1 [그리디] 개념 정리 및 활용 사례 (Feat. 최소 신장 트리 & 배낭 문제) 그리디 개념그리디는 '탐욕스러운'이라는 영단어 뜻처럼, 문제 해결 과정에서 결정하는 순간마다 눈 앞에 보이는 최선의 선택을 하는 알고리즘을 말합니다. 이러한 특성으로 인해 '지역 최적해를 추구한다'고 생각할 수 있습니다. 그리디 알고리즘은 부분적으로는 최적해, 전체적으로는 최선의 해를 구합니다. 그리디 알고리즘은 아래 2가지와 같은 특정 상황에서 최적해를 보장합니다. 1. 최적 부분 구조 : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치2. 그리디 선택 속성 : 선택 과정이 다른 과정에 영향을 주지 않음 위 조건을 만족하는 경우, 최적해를 도출하지만,조건을 만족하지 않는 경우, 현재의 최적의 결정이 이후 선택에 제약이 될 수 있으므로,항상 최적해를 도출하지 못한다는 한계가 있습니다. 그리디 알고.. 2025. 4. 8. 이전 1 다음
