그리디 알고리즘

최근 알고리즘 공부를 대학교 동아리 스터디에서 진행하게 되었다. 스터디의 진행 방식은 유튜브를 통해 나동빈님의 알고리즘 강의를 보고, 내용을 정리, 주어진 문제를 파이썬으로 푸는 방식이다. 이때 정리한 내용을 동아리 Notion 페이지에 올리게 되는데, 추후 따로 다시 공부하거나, 또 훗날 누군가 이 velog 글을 보며 공부할 때를 위해 알고리즘을 정리한 글을 velog에 남기려 한다. 이제 시작해 보자. 참고한 강의는 아래의 강의이다. https://youtu.be/5OYlS2QQMPA?si=77wCe6SQRnNbqIA7

그리디 알고리즘

그리디 알고리즘이란

그리디 알고리즘이란 Greedy(탐욕적인)라는 이름답게, 단순히 현재의 주어진 상황에서 가장 나은 선택지를 구하는 것, 즉 최적해를 구하는 것이다. 그리디 알고리즘은 그 간단한 원리로 인해, 문제를 풀기 위해 최소한의 아이디어를 떠올릴 수 있는 능력만을 요하나, 그 해법을 어떠한 근거로 찾아내었는지의 정당성이 중요하다.

이해를 위한 예제

그리디 알고리즘을 이해하기 위해서, 다음과 같은 문제 상황을 보자.

(참고) 트리 구조의 명칭(아래)

위의 문제와 같은 상황에서, Greedy하게 해를 찾자. 루트 노드로부터 그 다음 자식 노드로 내려가며 그리디 알고리즘을 사용하면, 레벨 1 노드들 중에서는 7, 10, 8 중 10을, 선택한 10의 자식 노드인 레벨 2 노드들 중에서는 4, 3 중 4를 택할 것이다. 총합은 5(루트) + 10 + 4로 19가 되어, Global한 최적해와 근사한 값을 빠르게 찾을 수 있게 된다.

단점

그러나 위의 문제를 다시 보면, 전역적으로 조합할 수 있는 가장 큰 값은 5 + 7 + 9의 21이 된다. 이것이 일반적인 상황에서 그리디 알고리즘의 한계이다. 그리디 알고리즘은 단지 상황판단의 상황에서 근시안적으로 최적해를 탐색하므로, Global에서는 최적의 값이 아닐 수 있다.

사용

위와 같은 단점으로 인해, 그리디 알고리즘은

• 탐욕 선택 속성(greedy choice property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

위의 조건을 만족하지 않는 경우, 최적의 해를 보장하지 못한다.

그래서 최적의 결과를 도출하는 것이 목표가 아닌, 최적에 근사한 값을 빠르게 도출하기 위해, 근사 알고리즘(Approximation Algorithm, 최적해가 아닌 비교적 빠른 시간 내 보장된 근사해를 계산)으로 그리디 알고리즘을 활용한다.