오늘은 그리디 알고리즘에 대해 수강하였다.
오늘 내용은 그리 길지 않다.
그리디 알고리즘 이란?
매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘으로써 최적해를 보장하진 않지만
선형시간이 소요되는 알고리즘이다.
최적해를 고려하지않으므로 알고리즘이 굉장히 빠르고, 직관적인 문제 풀이에 적합하다.\
작동방식은 양자택일 or 다자택일 상황에서 가장 빠른 알고리즘만을 찾아서 진행한다.
그렇기 때문에 최종시간은 최적해를 구하는 알고리즘보다는 오래 걸리게 된다.
예시로는 동전반환문제가 있는데, 이 동전반환 문제가 그리디 알고리즘을 이해하기 가장 쉽다고한다.
가장 큰 액수부터 차감하여 작은 액수까지 진행된다.
그리디 알고리즘은 특정 개념이라고 알고있는 것이 좋다.
'알고리즘 > 알고리즘' 카테고리의 다른 글
| 알고리즘 강의 17일차 - 재귀함수 (0) | 2023.03.28 |
|---|---|
| 알고리즘 강의 16일차 - 소수 알고리즘 (0) | 2023.03.24 |
| 알고리즘 강의 14일차 - BFS, DFS (0) | 2023.03.22 |
| 알고리즘 강의 13일차 - 정렬의 기초 (0) | 2023.03.21 |
| 알고리즘 강의 12일차 - 이진탐색 기초 (0) | 2023.03.20 |