그리디 알고리즘(greedy algorithm)

10월 첫째주부터 매주 목요일에 알고리즘을 공부하는 스터디를 시작했습니다. 공부한 내용을 정리할겸 블로그에도 그 흔적을 남겨보려고 합니다.

그리디 알고리즘 (Greedy Algorithm)

개념

그리디 알고리즘, 혹은 탐욕 알고리즘이라고 부르는 이 알고리즘은 선택의 순간마다 그 순간에 최적이라고 생각되는 선택지를 택해 최종적인 최적해에 도달하는 기법을 뜻합니다.

특징

그리디 알고리즘은 여러 경우의 수 중 하나를 고를 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행해서 최종적인 해답에 도달합니다. 오직 그 순간만을 고려하기 때문에, 선택한 답이 그 순간에 대해 지역적으로는 최적해지만 전역적으로 봤을 때도 최적의 답이라는 보장은 없습니다.

장단점

앞서 말했듯이 그리디 알고리즘은 오직 지금 이 순간만을 고려합니다. 그렇기 때문에 전역적으로 봤을 때도 최적의 답이라는 보장이 없다는 것이 단점으로 작용합니다.

예를 들어 가장 적은 동전 갯수로 거스름돈을 남겨줘야 한다고 가정해봅시다. 남겨줘야할 거스름돈은 710원이라고 해보죠. 우리가 가진 동전의 종류는 다음과 같습니다.

[10, 100, 500]

그리디 알고리즘식으로 접근하면, 가장 적은 갯수로 해당 금액을 만들려면 가장 큰 금액의 동전인 500원을 선택할 것입니다. 2개가 있으면 목표금액을 넘으니까 500원짜리 동전은 단 하나가 필요합니다.

500 x 1

이번 선택의 순간에는 이제 그 다음으로 큰 동전인 100원짜리를 고를 것입니다. 100원 짜리를 더 고를 수 없게 되면 마지막으로 10원짜리 동전을 고르게 되겠죠.

500 x 1 100 x 2 10 x 1

이 경우는 그리디 알고리즘으로 구한 답이 최종적인 답과 일치합니다.

그러나, 우리가 가진 동전이

[100, 300, 400, 500] 원일 때 700원을 거슬러줘야한다면 어떨까요?

500 x 1 100 x 2

이 경우 그리디 알고리즘으로 답을 구하면 필요한 동전 갯수는 3개입니다. 그러나, 사실은 300원짜리 1개, 400원짜리 1개 총 2개만으로 700원을 만들 수 있습니다. 선택의 순간에는 500원짜리 동전을 고르는 것이 최선의 선택이었지만, 결과적으로는 최선의 선택이 아니었던 겁니다. 그리디 알고리즘의 단점이 명확히 드러나는 상황이죠.

그렇다면 이렇게 확실한 보장이 없는 그리디 알고리즘을 왜 사용할까요? 바로 간단하고 쉽기 때문입니다. 항상 성공하는 것은 아니지만, 구현이 간단하면서도 보통은 정답에 상당히 가까운 정답을 도출해내죠.

정확한 답을 계산하는 데 시간이 너무 많이 걸리는 문제를 풀 때 근사 알고리즘(approximation algorithm)을 사용할 수 있는데요, 그리디 알고리즘은 근사 알고리즘 디자인 테크닉의 한 방법이 될 수 있습니다.

참고자료

코드없는 프로그래밍 - 코딩테스트, 기초, Greedy 탐욕 알고리즘(youtube)
Letsgo - 탐욕 알고리즘
Hanamon - [알고리즘] 탐욕 알고리즘(Greedy Algorithm)
Luna Young - 탐욕 알고리즘 / Greedy Algorithm