[파이썬 알고리즘] 그리디 알고리즘 개요

업데이트: July 01, 2022

현재 상황에서 지금 당장 좋은 것만 고르는 방법을 말한다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로나 가장 작은 순서대로와 같은 기준을 제시해준다.

대체로 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이뤄 문제가 출제되는 편이다.

정당성 분석의 중요성

단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는 과정이 필요하다.

[ 문제 ] 위에서부터 시작하여 거쳐 가는 숫자의 합을 최대로 만드시오.

위와 같이 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제되므로 알맞은 문제에 사용하도록 하자.

Notice: 이 게시물은 한빛미디어의 이것이 코딩 테스트다 영상과 교재를 참고하였습니다.

참고