[Python 알고리즘] # 그리디

그리디 알고리즘이란?

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법입니다.
탐욕법으로도 소개되는 이 알고리즘은 단순 무식하고, 탐욕적으로 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미합니다.
그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.

그리디 알고리즘에서의 최선의 선택이란?

• 그리디 알고리즘에서 추구하는 가장 좋은 것을 예시를 들어 설명해보면,

시작 지점에서 6을 거쳐 128로 가는 경로가 가장 큰 수를 출력할 수 있는 Best 경로임을 알 수 있습니다.
그리디 알고리즘을 사용하면 현재 상황에서 가장 좋은 방법을 선택하므로 시작 지점에서 현재 가장 큰 수인 17을 선택하고 이어서 23을 선택하게 됩니다.
결론적으로 그리디 알고리즘은 '시작 - 17 - 23' 경로가 가장 좋은 것이라고 판단합니다.

그리디 알고리즘이 가진 특징

• 정렬, 최단 경로 등의 알고리즘과 달리 사용 방법을 사전에 외우지 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있습니다.

• 그리디 알고리즘 유형의 문제는 매우 다양하기 때문에 암기한다고 해서 잘 풀 수 있는 알고리즘 유형이 아닙니다.

• 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해줍니다. 이러한 특징으로 그리디 알고리즘 문제는 주로 정렬 알고리즘과 짝을 이뤄 출제됩니다.

참고자료

이것이 코딩 테스트다 with 파이썬