그리디 알고리즘이 어려운 이유는 구현이 어려워서가 아니라, 맞아 보이는 선택이 실제로 항상 맞는지 확신하기 어렵기 때문입니다. 많은 사람이 문제를 읽고 “이건 가장 큰 것부터 고르면 되겠네” 같은 직감을 떠올리지만, 제출하면 틀리는 이유가 바로 여기에 있습니다.
이번 글에서는 그리디를 단순한 “현재 최선 선택”으로 설명하지 않고, 왜 그 선택이 항상 맞는지 정당화해야 하는 문제로 보겠습니다. 반례를 보는 습관, 정당화 방식, DP나 완전탐색과의 경계까지 함께 정리하겠습니다.
왜 직감은 자주 맞아 보일까
그리디 문제는 작은 예시에서는 직감이 맞는 경우가 많습니다. 입력이 작으면 미래 손해가 아직 드러나지 않기 때문입니다. 그래서 “당장 가장 좋아 보이는 선택”이 전체 최적처럼 보입니다.
예를 들어 동전 거스름돈 문제에서 큰 단위 동전부터 쓰는 전략은 몇몇 체계에서는 정말 잘 맞습니다. 하지만 동전 체계가 바뀌는 순간 그 직감이 바로 깨질 수 있습니다. 즉 작은 예시에서 맞았다는 사실은 그리디의 정당화가 아닙니다.
그리디가 자주 틀리는 진짜 이유
- 현재 최선이 미래 선택을 망칠 수 있다
- 선택 기준이 예시에서는 좋아 보여도 전체 구조와 안 맞을 수 있다
- 반례를 못 보면 잘못된 규칙을 너무 빨리 일반화하게 된다
- “코드가 간단하다”는 이유로 맞는 알고리즘처럼 착각하기 쉽다
즉 그리디의 난점은 선택을 빨리 하는 데 있지 않습니다. 그 선택이 전체 최적을 깨지 않는다는 보장을 잡기 어렵다는 데 있습니다.
반례를 못 떠올리면 왜 오답이 반복될까
많은 오답은 “직감은 좋은데 반례를 못 본 경우”에서 나옵니다. 현재 가장 좋아 보이는 선택이 다음 선택지를 나쁘게 만들 수 있는데, 그 구조를 미리 떠올리지 못하는 것입니다.
- 현재 최선이 미래 선택을 제한하는가
- 작은 입력에서는 맞아도 큰 입력에서 깨지는가
- 선택 순서를 바꾸면 더 좋은 결과가 나오는가
- 로컬 최적이 글로벌 최적을 보장하는 구조인가
이 질문을 안 던지면 그리디는 거의 운에 기대는 풀이가 됩니다. 그래서 그리디를 잘하는 사람은 아이디어를 빨리 떠올리는 사람이 아니라, 아이디어를 의심할 줄 아는 사람인 경우가 많습니다.
간단한 반례 예시로 감각 잡기
예를 들어 동전이 1, 3, 4이고 목표 금액이 6이라고 해보겠습니다. 큰 동전부터 고르면 4 + 1 + 1로 3개를 쓰게 됩니다. 하지만 최적해는 3 + 3으로 2개입니다.
이 예시는 “큰 것부터 고른다”는 직감이 항상 안전하지 않다는 것을 보여줍니다. 즉 그리디의 핵심은 규칙을 만드는 것이 아니라, 그 규칙이 깨지지 않는 문제 구조를 찾는 것입니다.
그리디 정당화는 무엇을 뜻할까
정당화는 단순히 “그렇게 풀면 될 것 같다”가 아닙니다. 왜 현재 선택이 전체 해를 망치지 않는지 설명하는 일입니다. 문제에 따라 교환 논법, 정렬 기준의 타당성, 항상 최적 부분을 남기는 이유 같은 설명이 필요할 수 있습니다.
예를 들어 회의실 배정 문제에서 종료 시간이 가장 빠른 회의를 먼저 고르는 전략은, 더 늦게 끝나는 회의를 먼저 고른 것보다 이후 선택 가능성을 덜 줄인다는 식으로 설명할 수 있습니다. 이런 설명이 바로 정당화입니다.
그리디 개념 참고를 보면 현재 이득이 큰 선택을 쌓는 방식이라는 설명이 먼저 나오지만, 실전에서는 그 선택이 왜 항상 안전한지까지 확인해야 비로소 풀이가 완성됩니다.
그리디와 DP는 어디서 갈릴까
그리디는 “지금 이 선택을 해도 나중에 후회하지 않는다”는 확신이 있을 때 강합니다. 반면 DP는 현재 선택이 미래 상태에 어떤 영향을 줄지 전부 고려해야 할 때 필요합니다.
즉 같은 최적화 문제라도 현재 선택이 미래 상태를 강하게 바꾸고, 그 영향을 단순 규칙 하나로 설명하기 어렵다면 DP 쪽일 가능성이 큽니다. 반대로 현재 선택을 해도 이후 문제 구조가 깔끔하게 유지된다면 그리디 가능성이 커집니다.
비슷한 판단 축은 DP 글과 비교하면 더 또렷합니다.
그리디와 완전탐색은 어디서 갈릴까
완전탐색은 가능한 선택을 거의 다 보면서 정답을 확인하는 방식입니다. 그래서 느리지만 안전합니다. 반면 그리디는 선택 가지를 과감히 버립니다. 따라서 가지를 버려도 안전한 이유가 있어야 합니다.
만약 선택을 줄이는 명확한 이유를 설명하지 못한다면, 그리디로 빨리 가려는 시도보다 완전탐색이나 백트래킹 쪽이 더 정직한 접근일 수 있습니다.
이 차이는 DFS와 백트래킹 글을 함께 보면 더 분명해집니다.
문제를 읽을 때 스스로 던질 질문
- 지금 가장 좋아 보이는 선택이 미래 선택을 줄이지 않는가?
- 선택 기준을 바꾼 반례를 쉽게 만들 수 없는가?
- 이 문제는 정렬 후 한 방향으로 훑으면 구조가 단순해지는가?
- 현재 선택 이후에도 남은 문제가 같은 모양으로 유지되는가?
이 네 질문에 대한 답이 선명할수록 그리디 가능성이 높아집니다. 반대로 답이 흐리면 그리디를 의심해야 합니다.
실전에서 자주 하는 실수
- 예제 몇 개가 맞는다고 정당화까지 끝났다고 착각한다
- 정렬 기준이 왜 맞는지 설명 없이 외워서 적용한다
- 그리디 문제를 반례 검증 없이 바로 구현한다
- 사실은 DP나 백트래킹 문제인데 그리디처럼 밀어붙인다
그리디는 직감형 문제가 아니라 검증형 문제라고 생각하면 이런 실수를 많이 줄일 수 있습니다.
마무리
그리디 알고리즘이 어려운 이유는 아이디어가 빨리 떠올라서가 아니라, 그 아이디어가 정말 항상 맞는지 확인하기 어렵기 때문입니다.
즉 그리디 문제에서 가장 중요한 습관은, 직감적으로 고른 선택이 왜 항상 안전한지 설명할 수 있는가를 끝까지 확인하는 일입니다.
