그리디 알고리즘(Greedy Algorithm)
“Greedy(그리디)”는 영어로 ‘탐욕스러운’, ‘욕심 많은’이라는 뜻을 가지고 있습니다. 마치 눈앞의 이익만을 좇는 사람을 ‘탐욕스럽다’고 하듯, 그리디 알고리즘도 문제를 해결할 때 매 순간 가장 좋아 보이는(즉, 가장 이득이 되는) 선택만을 반복적으로 고릅니다. 그래서 이를 ‘그리디’ 혹은 ‘탐욕법’이라고 부릅니다.
현실에서 ‘탐욕스럽다’는 말은 보통 부정적인 의미를 가지지만, 알고리즘에서의 탐욕은 “현재 상황에서 최선”의 선택을 이어가는 전략을 의미합니다. 전체를 보는 대신 지금 이 순간만 보고 결정하는 것, 이것이 바로 그리디 알고리즘의 핵심입니다.
이 전략은 마치 배가 고픈 사람이 눈앞에 있는 가장 큰 음식부터 집어 먹는 상황과 비슷합니다. 이 사람은 전체 식단이나 영양 균형은 고려하지 않고, 지금 당장 가장 만족스러워 보이는 것부터 선택합니다.
그리디 알고리즘도 이와 마찬가지로 매번 가장 좋아 보이는 선택을 반복합니다.
물론, 이런 탐욕적인 선택이 항상 정답으로 이어지는 것은 아닙니다. 그리디 알고리즘이 제대로 작동하기 위해선 몇 가지 조건이 충족되어야 하며, 그렇지 않다면 최적의 답를 놓칠 수도 있습니다.
적용 조건
그리디 알고리즘은 코드가 간결하고 빠르지만, 모든 문제에 적용 가능한 것은 아닙니다. 다음 두 조건을 충족하지 못하면, 잘못된 결과가 나오거나 전체 문제의 답이 나오지 않을 수 있습니다.
- 지금 선택이 전체 최적의 일부가 되는가? → 선택 순서를 바꿔도 더 나은 결과가 나오는지 확인
- 문제를 쪼개서 풀고 다시 합쳐도 최적인가? → 작은 문제들도 독립적으로 최적해를 가질 수 있는 지 확인
주의 사항
그리디는 조건이 맞지 않으면 오히려 전체적으로는 잘못된 선택이 될 수 있습니다. 선택을 되돌릴 수 없기 때문에 초기의 잘못된 선택으로 전부 틀어질 수 있으므로, 그리디를 쓰기 전에 다음 사항을 체크해보는 것이 좋습니다.
- 선택 기준이 명확한가?
- 정렬을 통해 선택 순서를 만들 수 있는가?
- 선택을 고정했을 때, 이후 문제에 영향이 없나?
- 작은 문제들을 최적으로 해결해도, 큰 문제 전체에서 최적인가?
- 예외 상황이나 반례는 없는가?
작동 방식
대부분의 그리디 문제는 선택 기준이 명확한 순서를 따릅니다. 따라서 지금 가장 좋아 보이는 답을 선택하기 위해 먼저 정렬을 하는 게 거의 필수입니다. 만약 선택 기준이 명확하지 않다면 그리디가 아닐 수 있습니다. 그리디라는 확신이 들면 다음 순서에 따라 풉니다.
- 문제를 여러 단계로 나눕니다. → 한 번에 하나씩 선택하며 문제를 해결할 수 있도록 분할
- 각 단계에서 가능한 선택지 중에서 가장 좋은 것을 고릅니다. → 문제에 맞춰 가장 큰, 가장 작은, 가장 빠른 등
- 그 선택한 결과를 확정하고, 남은 문제에 대해서도 같은 방식으로 반복합니다. → 뒤로 가지 않고, 선택한 결과는 취소하지 않음 (백트래킹 ❌, 전체 계산 ❌)
- 이 과정을 문제 해결이 끝날 때까지 이어갑니다.
🆚 DP(다이나믹 프로그래밍)
그리디와 DP는 문제를 푸는 목표는 같지만 방식이 완전히 다릅니다. 최적의 결과라는 목표가 같으므로 둘 다 접근이 가능합니다. 문제를 마주쳤을 때 어떤 알고리즘을 적용할 지 선택해야 합니다.
그리디는 빠르지만 조건이 까다롭고, 정답이 아닐 수 있습니다. DP는 느리지만 항상 정답을 찾을 수 있습니다. 대부분 문제를 마주쳤을 때 ‘그리디가 안 통하면 DP로 가야겠다’라는 사고의 흐름으로 풉니다😁.
💡 그리디 알고리즘 코딩테스트 문제 풀이
