[공부][알고리즘] 탐욕 알고리즘 (Greedy Algorithms)

알고리즘을 공부하다 보면 가장 직관적이고 현실의 의사결정과 비슷한 방식이 바로 탐욕 알고리즘이다.

 

오늘은 최적화 문제를 해결하는 핵심 접근법 중 하나인 탐욕 알고리즘의 개념과 동작 원리, 알고리즘 복잡도, 그리고 이 알고리즘이 언제나 최적해를 보장하는지 그 한계점에 대해 분석해보겠다.

 

1. 개념

탐욕 알고리즘은 전체적인 미래를 내다보고 계획을 세우는 것이 아니라

당장 현재 상태에서 가장 이득이 되는 선택을 순차적으로 해 나가는 알고리즘이다.

 

최적화 문제는 전체 비용을 최소화하거나 전체 이익을 최대화하는 것을 목표로 한다.

탐욕 알고리즘은 이러한 목표를 달성하기 위해 문제의 각 단계마다 단기적인 기준에 따라 가장 최선이라고 판단되는 것을 선택한다.

 

평가하기에 너무 많은 비용이 들지 않는 단순한 기준을 바탕으로, 매 순간 가장 좋아 보이는 요소를 찾아 결과에 추가하는 직관적인 방식을 사용한다.

---

2. 내부 동작 원리

탐욕 알고리즘은 현재 상태에서 가장 이득이 되는
단기적인 기준에 따라 개별적인 선택을 진행한다.

 

이때 사용하는 선택 기준은 복잡하지 않고 평가하기에 많은 비용이 들지 않아야 한다는 특징이 있다.

가장 중요한 원칙은 한 번 내려진 결정은 이후에 다시 되돌리거나 취소할 수 없다는 비가역성이다.

 

비록 당장의 이익을 좇는 행위가 나중에 피할 수 없는 더 큰 손실을 초래할 수 있다는 치명적인 단점이 있으나, 규칙이 맞는 특정 문제에서는 매우 빠르고 정확한 정답을 구할 수 있다.

https://brilliant.org/wiki/greedy-algorithm/

 

첨부된 트리 구조 이미지를 통해 탐욕 알고리즘이 최적해를 찾지 못하는 치명적인 한계를 쉽게 이해할 수 있다.

 

맨 위의 루트 노드에서 출발하여 아래로 내려가면서 방문하는 노드 숫자의 합을 가장 크게 만드는 최적화 문제를 가정해 보자.

탐욕 알고리즘을 사용한다면 매 순간 가장 큰 숫자가 있는 쪽만 선택하게 된다.

 

시작점인 7에서 다음으로 갈 수 있는 노드는 3과 12인데, 탐욕 알고리즘은 당장 더 커 보이는 12를 선택한다.

그 다음 12에서는 5와 6 중 더 큰 6을 선택하여, 최종 경로는 7, 12, 6이 되고 총합은 25가 된다.

하지만 전체 트리를 살펴보면 실제 최적해는 다르다. 시작점 7에서 비록 당장은 작아 보이는 3을 선택하더라도 그 길을 따라가면 99를 만나게 되어, 최종 경로는 7, 3, 99가 되고 총합 109라는 훨씬 더 큰 결과를 얻을 수 있다.

 

한 번 12를 선택한 순간 99로 갈 수 있는 길을 영영 잃어버리는 비가역성 때문에 오답을 내는 것이다.

 

하지만 이런 한계에도 불구하고 탐욕 알고리즘이 완벽하게 작동하는 사례도 있다.

임의의 그래프 구조에서 모든 정점을 가장 적은 비용으로 연결하는 최소 비용 신장 트리(MST) 문제를 생각해보자. 탐욕 알고리즘을 적용한 대표적인 사례가 바로 크루스칼 알고리즘이다.

 

크루스칼 알고리즘은 전체 간선 중에서 가중치가
가장 낮은 간선부터 차례대로 살펴보며 연결을 시도한다.

 

이때 당장의 비용이 가장 적은 간선을 우선적으로 선택하되, 그 간선을 연결했을 때 정점들 사이에 순환하는 고리인 사이클이 생기지 않는 경우에만 최종적으로 선택을 확정한다.

 

의사 코드로 표현하면 다음과 같다.

KruskalMST(G, n) 
R = 전체 간선들의 집합 
F = 비어있는 최종 트리 간선 집합

while (R이 비어있지 않음) { 
R에서 가중치가 가장 작은 간선 vw를 꺼내어 제거한다.
	if (간선 vw가 F 안에서 사이클을 만들지 않는다면) {
    	간선 vw를 F에 추가한다.
	}
}

return F

 

위 코드에서 while 반복문은 정렬된 간선들을 가장 비용이 적은 것부터 하나씩 확인하는 역할을 하고,

if 조건문은 탐욕적 선택이 트리의 기본 규칙을 위반하지 않는지 검사하는 역할을 수행한다.

 

이처럼 매번 남은 것 중 가장 짧고 가벼운 간선을 선택하는 행위를 반복하여 정답을 도출한다.

---

3. 복잡도 분석

이 알고리즘이 얼마나 효율적으로 동작하는지 시간 복잡도를 기준으로 측정해 볼 수 있다.

크루스칼 알고리즘을 기준으로 살펴보면 가장 먼저 모든 간선을 가중치의 오름차순으로 정렬하는 과정이 필요하다.

 

그래프에 존재하는 간선의 개수를 E라고 할 때 정렬에 소요되는 시간은 점근적 표기법으로 O(E log E)가 된다.

 

이후 각 간선을 하나씩 꺼내어 사이클 발생 여부를 확인하기 위해 서로소 집합(Disjoint Set) 자료구조를 사용한다.

이 사이클 판별 및 병합 연산은 매우 빠른 속도로 처리되므로 전체 알고리즘의 수행 시간은 사실상 초기의 간선 정렬 과정에 의해 지배된다.

 

결과적으로 탐욕 알고리즘은 각 단계에서의 선택 기준이 단순하여 평가하고 결정하는 비용이 낮으므로, 모든 경우의 수를 탐색하는 방식보다 훨씬 빠르고 효율적인 실행 속도를 보여준다.

---

4. 수학적 최적성과 한계

매 순간 눈앞의 이득만을 좇는 최고의 선택을 한다고 해서 그것이 모인 최종 결과가 항상 전체의 최고를 보장하는 것은 아니다.

 

단기적인 기준에서는 비용이 가장 적게 드는 최선의 행동이었지만, 그 선택으로 인해 나중에는 피할 수 없는 매우 큰 비용을 감당해야만 하는 상황에 직면할 수도 있다.

 

비가역성이라는 태생적 성질 때문에 한 번 잘못된 경로로 빠지면 최적해를 찾지 못하고 종료되는 한계가 명확히 존재한다.

 

놀랍게도 그래프의 최소 비용 신장 트리 문제나 다익스트라를 이용한 단일 출발점 최단 경로 문제 등

특정한 수학적 조건을 만족하는 환경 안에서는 이러한 탐욕적 선택만으로도 언제나 전체의 최적해를 정확히 찾아낸다.

 

즉 탐욕 알고리즘은 어떠한 문제든 무조건 해결해 내는 만능은 결코 아니며,

국소적인 최적이 전체의 최적으로 이어지는 수학적 한계와 구조를 정확히 파악하고 사용할 때 비로소 가장 빠르고 강력한 최적화 알고리즘으로 동작한다.

---

마무리

탐욕 알고리즘은 계산 과정이 단순하고 직관적이라는 강력한 장점이 있다.

 

하지만 살펴본 트리 예시처럼 단기적인 최선이 항상 전체의 최선으로 이어지는 것은 아니므로, 주어진 문제가 탐욕적인 선택으로 해결 가능한지 증명하고 판단하는 안목이 반드시 필요하다.

 

따라서 알고리즘의 긍정적인 원리를 이해하는 것과 더불어 어떠한 경우에 이 방식이 철저히 실패하는지 그 한계점과 구조적 특성을 명확히 인지하는 것이 바람직하다.