탐욕 알고리즘 (Greedy Algorithm)

한 줄 정의: 전체를 다 따져보지 않고 매 단계에서 지금 당장 가장 좋아 보이는 선택을 계속 반복해서 답을 구하는 알고리즘입니다.

쉽게 풀면

거스름돈을 줄 때를 생각해봅시다. 1,270원을 거슬러줘야 한다면 대부분 사람은 일단 가장 큰 동전(500원)부터 최대한 많이 집고, 남은 금액에서 또 가장 큰 단위를 집는 식으로 계산합니다. 나중에 손해를 볼지 안 볼지 미리 다 계산해보지 않고, "지금 이 순간 가장 큰 걸 집는 게 이득"이라는 판단만으로 끝까지 밀어붙이는 것이죠. 탐욕 알고리즘이 바로 이런 방식입니다. 매 순간 눈앞의 최선만 선택하기 때문에 계산이 빠르고 간단하지만, 상황에 따라서는 전체적으로 봤을 때 최선이 아닌 답에 도달할 수도 있다는 점이 특징입니다.

왜 중요한가

탐욕 알고리즘은 모든 경우의 수를 따지지 않고도 빠르게 답을 얻을 수 있어, 대규모 데이터나 실시간 처리가 필요한 문제에서 정확한 최적해 대신 실용적인 근사해를 구하는 대표적인 전략으로 다뤄집니다. 최소 신장 트리, 허프만 부호화처럼 탐욕적 선택이 실제로 최적해를 보장하는 문제들이 알려져 있어, 어떤 문제 구조에서 탐욕 전략이 통하는지를 분석하는 것 자체가 알고리즘 이론의 중요한 주제이기도 합니다.

논문에서는 이렇게 쓰입니다

"제안 모델은 매 시점마다 지역적으로 보상이 가장 큰 행동을 선택하는 탐욕 알고리즘(greedy algorithm)을 적용하여 계산 복잡도를 크게 낮추었다."

이 문장은 최적해를 정확히 찾기 위해 모든 경우의 수를 따지는 대신, 매 단계에서 가장 유리해 보이는 선택만 빠르게 이어감으로써 계산 시간을 줄였다는 뜻입니다. 자원 스케줄링, 네트워크 라우팅, 특징 선택(feature selection) 등 근사해로도 충분하거나 속도가 중요한 문제에서 자주 사용됩니다.

"클러스터 내 작업 스케줄링에서는 대기 중인 작업 중 처리 시간이 가장 짧은 작업을 우선 배정하는 탐욕 방식을 채택하였다."

분산 시스템 연구에서 자원 배정 문제를 탐욕적으로 접근해 스케줄링 지연을 줄인 예시입니다.

"강화학습 탐색 과정에서 일정 확률로 무작위 행동을 섞은 엡실론-탐욕(epsilon-greedy) 전략을 사용하여 탐색과 활용의 균형을 맞추었다."

강화학습 연구에서 순수한 탐욕적 선택에 약간의 무작위성을 더한 변형 전략을 적용한 예시입니다.

조금 더 깊게 보면

탐욕 알고리즘이 실제로 전체 최적해를 보장하는지는 문제가 특정한 수학적 구조(대표적으로 매트로이드 구조)를 만족하는지에 따라 갈립니다. 이런 구조가 성립하지 않는 문제에서는 탐욕적 선택이 국소적으로는 최선이어도 전체적으로는 최적에서 벗어날 수 있어, 논문에서는 흔히 탐욕 알고리즘이 낸 해가 최적해와 얼마나 차이 날 수 있는지를 이론적으로 보이거나 실험으로 확인하는 절차를 함께 제시합니다.

주의할 점

탐욕 알고리즘은 항상 최적의 답을 보장하지 않습니다. 매 순간의 최선이 전체의 최선으로 이어지는 문제(예: 최소 신장 트리)에서는 잘 작동하지만, 그렇지 않은 문제에서는 부분 최적해에 그칠 수 있습니다. 이런 경우에는 모든 부분 문제의 결과를 저장하고 재활용하는 동적계획법이나, 문제를 쪼개서 각각 해결한 뒤 합치는 분할정복 방식이 더 정확한 답을 줄 수 있습니다.