개발새발
탐욕 알고리즘(Greedy) 본문
탐욕 알고리즘 (Greedy)
- 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황을 선택해서 답을 찾는것
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복
- 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다
- 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립해야한다
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않아야한다
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성해야한다
'알고리즘' 카테고리의 다른 글
#탐욕알고리즘 #짐나르기 #편의점알바 #자리 옮기기# 금고털기 (0) | 2022.08.03 |
---|---|
#의사코드 #시간복잡도 (0) | 2022.08.03 |
#Tree #Graph # BST (0) | 2022.08.03 |
# 스택 #큐 (0) | 2022.08.03 |
Comments