1주차 - 그리디 이론

정의 ‘탐욕스러운’ 혹은 ‘욕심 많은’을 뜻하는 알고리즘으로 선택의 순간마다 바로 눈앞에 보이는 이익만을 좇는 알고리즘을 뜻합니다. 즉, 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법을 말합니다. 결정을 내리는 순간마다 가장 최선의 선택을 통해 전체적인 최적의 해결책을 찾아내고자 하는 노력에서 비롯되었습니다. 각 단계에서의 최선의 선택이 결국 전체적인 최적의 해결책을 제공해주는 경우가 많습니다. 동적 프로그래밍을 사용하게 되면 중복되는 하위 문제를 다루게 되는데 이것이 많은 연산량과 계산 복잡도가 커지게 한다는 한계점을 가지고 있습니다. 이러한 점에 착안하여 고안된 알고리즘입니다. (동적 프로그래밍을 대체하는 것이 아닌 서로 보완하는 개념입니다) 특징 대부분의 경우 계산 속도가 빠르므로 매우 실용적..