그리디라는 사전적 의미는 "탐욕스러운" 이다.
즉, 탐욕적으로 "현재 상황에서 가장 베스트인 것만 고르는 방법"인 알고리즘이다.
부분 최적해가 모이면 전체 최적해가 되다는 알고리즘이다.
예를들어 서울 대구 부산을 지나간다고 가정을 해보자
(서울 - 대구 길에서 가장 빠른 길) + (대구 - 부산길에서 가장 빠른길)
를 찾아 더하면 최적해를 구할 수 있다.
이 알고리즘이 쓰이게 된 이유는 속도 때문이다.
완전탐색으로 정답을 찾게 되면 속도가 느리게 되니 DP 알고리즘을 사용하게 됐다.
하지만 DP프로그래밍도 항상 최적해를 보장하기 위해서 모든 경우의 수를 고려한다.
그러다보니 속도가 느려지게 된다.
그래서 항상 최적해를 찾는 그리디를 사용해 좀더 빠르게 문제를 풀 수 있게 되었다.
현실에서는 최적해가 아닌 근접값도 괜찮을 때 그리디 알고리즘을 사용한다고 합니다.
마침 유튜브에서 그리디 알고리즘을 설명한 것이 있는데
백준에서 그리디 문제를 모아놓은 것도 있어 링크도 같이 첨부하겠다.