이번 글에서는 알고리즘 설계 기법 중 가장 많이 비교되는 그리디(탐욕) 알고리즘과 동적 프로그래밍(Dynamic Programming)의 차이점을 자세히 살펴보겠습니다. 두 기법은 모두 복잡한 문제를 해결하기 위한 강력한 도구이지만, 문제에 접근하는 방식과 보장하는 결과가 크게 다릅니다.
그리디 알고리즘(Greedy Algorithm)이란?
그리디 알고리즘은 하나의 큰 문제를 작은 단계로 나누어, 각 단계마다 가장 눈에 보이는 즉각적인 이득을 주는 선택을 하는 방식으로 해를 점진적으로 구성해 나가는 알고리즘 설계 패러다임입니다.
- 지역 최적해 기반: 각 단계에서 지역적으로 최적인 값을 선택했을 때 전체 문제의 최적해(전역 최적해)로 이어질 수 있는 유형의 문제에 적합합니다.
- 최적해 보장 없음: 그리디 알고리즘이 반드시 최적의 해를 찾아준다는 보장은 없습니다.
- 단계별 최선의 선택: 문제의 모든 단계에서 국소적으로 최적인 선택, 즉 지역 최적해를 수행합니다.
- 메모리 효율성: 이전 결과로 되돌아가거나 수정할 필요가 없기 때문에 메모리 사용 측면에서 매우 효율적입니다.
- 빠른 실행 속도: 일반적으로 동적 프로그래밍 기법보다 실행 속도가 빠릅니다.
- 대표 예시: 다익스트라(Dijkstra) 최단 경로 알고리즘 — 시간 복잡도 O(E log V + V log V).
- 순방향 계산 방식: 해는 순방향으로만 계산되며, 이전 값이나 해를 다시 방문하거나 변경하지 않습니다.
동적 프로그래밍(Dynamic Programming)이란?
동적 프로그래밍은 하위 문제(sub-problem)의 결과를 저장해 두었다가, 나중에 동일한 하위 문제가 필요할 때 재계산하지 않고 미리 계산된 값을 그대로 활용하는 최적화 기법입니다. 이를 통해 지수(exponential)급 시간 복잡도를 다항식(polynomial)급으로 크게 줄일 수 있습니다.
- 재귀 → DP 변환: 예를 들어, 재귀적 풀이는 메모이제이션을 통해 동적 프로그래밍 문제로 손쉽게 변환할 수 있습니다.
- 이전 해의 활용: 매 단계의 결정은 현재 직면한 문제와 이미 풀어 놓은 하위 문제의 해를 함께 고려하여 최적값을 계산하는 방식으로 이루어집니다.
- 최적해 보장: 동적 프로그래밍으로 얻은 해는 최적이라는 것이 수학적으로 보장됩니다.
- 전역 최적해 추구: 선택되는 최적해는 전역적으로 최적인 해이며, 이전에 계산된 상태값을 저장하고 재사용하기 위한 점화식(공식)을 활용합니다.
- 메모이제이션 테이블 필수: 메모이제이션을 위해 DP 테이블이 필요하며, 이로 인해 메모리 복잡도가 증가합니다.
- 상대적으로 느린 속도: 그리디 알고리즘에 비해 실행 속도가 느린 편입니다.
- 대표 예시: 벨만-포드(Bellman-Ford) 알고리즘 — 시간 복잡도 O(VE).
- 상향식/하향식 접근: 최적해를 가진 더 작은 문제들로부터 답을 발전시켜 나가는 상향식(bottom-up) 또는 하향식(top-down) 방식으로 해를 결정합니다.
핵심 차이점 비교 요약
| 구분 | 그리디 알고리즘 | 동적 프로그래밍 |
|---|---|---|
| 선택 방식 | 매 단계 지역 최적 선택 | 이전 하위 문제의 해를 활용한 전역 최적 선택 |
| 최적해 보장 | 보장되지 않음 | 보장됨 |
| 실행 속도 | 일반적으로 빠름 | 상대적으로 느림 |
| 메모리 사용 | 효율적 | DP 테이블로 인해 추가 메모리 필요 |
| 계산 방향 | 순방향(앞으로만 진행) | 상향식 또는 하향식 |
| 대표 예시 | 다익스트라 O(E log V + V log V) | 벨만-포드 O(VE) |
마무리
정리하자면, 그리디 알고리즘은 속도와 메모리 효율이 뛰어나지만 최적해를 보장하지 않는 반면, 동적 프로그래밍은 추가 메모리와 더 많은 연산 시간을 희생하는 대신 반드시 최적해를 보장합니다. 따라서 문제의 구조가 그리디 선택 특성을 만족하는지(탐욕 선택 속성), 하위 문제가 반복되는지(최적 부분 구조)를 먼저 분석한 후, 문제의 성격에 맞는 기법을 선택하는 것이 중요합니다.