“Greedy(그리디)”는 영어로 ‘탐욕스러운’, ‘욕심 많은’이라는 뜻을 가지고 있습니다. 마치 눈앞의 이익만을 좇는 사람을 ‘탐욕스럽다’고 하듯, 그리디 알고리즘도 문제를 해결할 때 매 순간 가장 좋아 보이는(즉, 가장 이득이 되는) 선택만을 반복적으로 고릅니다. 그래서 이를 ‘그리디’ 혹은 ‘탐욕법’이라고 부릅니다.
현실에서 ‘탐욕스럽다’는 말은 보통 부정적인 의미를 가지지만, 알고리즘에서의 탐욕은 “현재 상황에서 최선”의 선택을 이어가는 전략을 의미합니다. 전체를 보는 대신 지금 이 순간만 보고 결정하는 것, 이것이 바로 그리디 알고리즘의 핵심입니다.
이 전략은 마치 배가 고픈 사람이 눈앞에 있는 가장 큰 음식부터 집어 먹는 상황과 비슷합니다. 이 사람은 전체 식단이나 영양 균형은 고려하지 않고, 지금 당장 가장 만족스러워 보이는 것부터 선택합니다.
그리디 알고리즘도 이와 마찬가지로 매번 가장 좋아 보이는 선택을 반복합니다.
물론, 이런 탐욕적인 선택이 항상 정답으로 이어지는 것은 아닙니다. 그리디 알고리즘이 제대로 작동하기 위해선 몇 가지 조건이 충족되어야 하며, 그렇지 않다면 최적의 답를 놓칠 수도 있습니다.
그리디 알고리즘은 코드가 간결하고 빠르지만, 모든 문제에 적용 가능한 것은 아닙니다. 다음 두 조건을 충족하지 못하면, 잘못된 결과가 나오거나 전체 문제의 답이 나오지 않을 수 있습니다.
그리디는 조건이 맞지 않으면 오히려 전체적으로는 잘못된 선택이 될 수 있습니다. 선택을 되돌릴 수 없기 때문에 초기의 잘못된 선택으로 전부 틀어질 수 있으므로, 그리디를 쓰기 전에 다음 사항을 체크해보는 것이 좋습니다.
대부분의 그리디 문제는 선택 기준이 명확한 순서를 따릅니다. 따라서 지금 가장 좋아 보이는 답을 선택하기 위해 먼저 정렬을 하는 게 거의 필수입니다. 만약 선택 기준이 명확하지 않다면 그리디가 아닐 수 있습니다. 그리디라는 확신이 들면 다음 순서에 따라 풉니다.