그리디 알고리즘
- 가장 간단하지만 가장 강력한 문제 해결 방법입니다.
- “탐욕의 법칙”이라고도합니다.
- 현재 상황에서 좋은 것만 선택하고 나중에 현재 선택의 의미를 고려하지 않는 것을 의미합니다.
- Dijkstra와 Floyd Warhall의 알고리즘은 욕심 많은 알고리즘으로 엄격하게 분류됩니다.
탐욕 알고리즘의 종류는 매우 다양하기 때문에 특별한 경우를 제외하고는 단순히 외우기만 하면 풀 수 있는 종류의 알고리즘이 아닙니다.
따라서 많은 유형의 탐욕스러운 알고리즘을 접하게 됩니다.
이것은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 기준을 직접 설정해야 합니다. B. “가장 큰 순서로” 및 “가장 작은 순서로”.
전)
예를 들어 그리디 알고리즘을 이해해 봅시다.
'추천 관련글,
위의 문제는 그리디 알고리즘을 이용하여 풀 수 있는 대표적인 문제이다.
해결 방법은 “가장 큰 화폐 단위에서 돈을 돌려주세요”오전.
- 먼저 500원만큼 N을 돌려준다.
- 그럼 얼마든지 돌려주세요, 100원.
- 그럼 얼마든지 돌려주세요, 50원.
- 그럼 10원 돌려드릴 수 있는 만큼 돌려주세요.
위 질문에 대한 답은 6번입니다.
코드로 구현하려면:
특성
- 그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 없습니다. → 대부분의 문제에서 그리디 알고리즘으로는 “최적 솔루션”을 찾을 수 없을 확률이 높습니다.
- 정답을 찾는 것이 보장될 때 매우 효과적이고 직관적입니다. → 즉, 그리디 알고리즘으로 문제를 풀 때 그 풀이가 유효한지 확인해야 한다.