그리디 - 지금 제일 좋아 보이는 것

거스름돈 3,700원을 줄 때 아무도 경우의 수를 따지지 않는다. 1,000원짜리 세 장, 500원 하나, 100원 둘. 큰 것부터 집으면 끝난다.

큰 동전부터 집는다

이 방식에는 규칙이 하나뿐이다. 지금 고를 수 있는 것 중 제일 좋아 보이는 것을 고르고, 되돌아보지 않는다.

int[] coins = {500, 100, 50, 10};
int count = 0;
for (int c : coins) {
    count += amount / c;      // 이 동전으로 최대한 집는다
    amount %= c;              // 남은 금액으로 다음 동전을 본다
}

갈림길이 셋이고 갈림길마다 후보가 셋이면 다 해볼 경우는 스물일곱인데, 그리디는 세 번 만에 끝난다.

되돌아보지 않아서 빠르다

다 해보는 방법과 비교하면 차이가 어디서 나는지 분명하다. 완전탐색은 갈림길마다 갈래가 벌어지지만, 그리디는 갈림길마다 하나만 골라 곧장 내려간다. 트리 전체가 한 줄이 된다.

그래서 대개 정렬 한 번에 훑기 한 번이라 n log n이면 끝나고, 코드도 짧다.

그런데 빠르기보다 중요한 게 하나 더 있다. 되돌아갈 준비를 안 해도 되니 들고 있을 것이 없다. 앞 글에서 본 방법은 나중에 쓸지 모르는 값을 표에 쌓아 두고 시간을 샀다. 그리디는 정확히 반대다. 아무것도 안 쌓고, 대신 한 번 지나간 자리로는 돌아갈 수 없다.

이 대가가 다음 절에서 청구된다.

그런데 동전 체계를 바꾸면 틀린다

여기가 이 글의 전부다. 같은 코드에 동전 종류만 바꿔 보자. 1원, 4원, 5원짜리가 있고 8원을 거슬러 준다.

큰 것부터 집으면 5원 하나에 1원 셋, 동전 넷이다. 그런데 4원 둘이면 동전 둘이다. 그리디가 진 게 아니라 틀린 답을 냈다.

무엇이 잘못됐을까. 5원을 집는 순간 남는 금액이 3원이 되고, 3원은 1원으로만 채울 수 있다. 지금 제일 커 보이는 것을 고른 대가를 나중에 치른 것인데, 고를 때는 그걸 알 방법이 없었다.

맞는지는 짐작이 아니라 증명으로 안다

그리디의 어려움은 짜는 데 있지 않다. 맞는지 아닌지를 아는 데 있다.

• 코드가 짧아서 틀렸을 때도 그럴듯하게 돌아간다. 예외도 안 나고 답도 나온다.
• 작은 입력에서는 대체로 맞는다. 반례가 특정한 모양일 때만 나타난다.
• 그래서 테스트를 통과하고 운영에 나간 뒤에 틀린 게 드러난다.

확인하는 방법은 둘이다. 하나는 “지금의 최선을 골라도 손해가 없다”를 논리로 보이는 것이고, 다른 하나는 작은 입력을 잔뜩 만들어 완전탐색과 답을 맞춰보는 것이다. 실무에서는 뒤엣것이 훨씬 자주 쓰인다. 반례가 하나 나오면 그리디는 그 문제에 못 쓴다.

⚠️ 반례가 안 나왔다고 맞는 건 아니다. 다만 반례 찾기를 진지하게 했는데 안 나왔다면 근거가 하나 생긴 것이고, 그건 “짜 보니 답이 맞더라”보다 훨씬 강하다.

그리디로 푸는 것으로 알려진 문제들

다행히 그리디가 맞는다고 증명된 문제들이 있고, 실무에서 만나는 것도 대개 그중 하나다.

• 회의실에 회의를 최대한 많이 넣기 - 끝나는 시각이 이른 것부터 고르면 최적이다. 시작이 이른 것부터 고르면 틀린다. 무엇을 기준으로 고르느냐가 맞고 틀림을 가른다는 것을 잘 보여주는 예다.
• 모든 지점을 잇는 가장 싼 연결망 - 싼 선부터 고르되 순환을 만드는 선만 건너뛴다.
• 가중치가 있는 그래프의 최단 경로 - 지금까지 알아낸 것 중 가장 가까운 지점부터 확정한다. 다익스트라라고 부르는 이 방법은 가까운 곳부터 훑는 너비 우선에 “가장 가까운 것”을 꺼내는 그릇을 붙인 것이고, 그 그릇이 힙이다.
• 자주 나오는 글자에 짧은 코드를 주는 압축 - 가장 드문 둘을 계속 묶어 올라간다.

⚠️ 다익스트라는 선의 값이 음수가 아닐 때만 맞는다. 음수가 있으면 “이미 확정한 지점”이 나중에 뒤집힐 수 있어서 그리디의 전제가 깨진다. 조건이 붙은 그리디라는 걸 잊으면 조용히 틀린 경로를 낸다.

틀린 줄 알면서 쓰기도 한다

그리디가 최적을 보장하지 않는데도 일부러 쓰는 경우가 있다. 최적을 구하는 게 현실적으로 불가능할 때다.

배달 경로를 정하는 문제처럼 후보가 n!로 폭발하는 문제들이 그렇다. 정확한 답을 구하려면 우주가 끝나도 안 끝난다. 이때는 그리디로 답을 하나 빨리 만들고, 그걸 조금씩 고쳐 나간다.

여기서 중요한 건 태도다. 최적이 아님을 알고 쓰는 것과, 최적인 줄 알고 쓰는 것은 코드가 같아도 전혀 다르다. 앞엣것은 “얼마나 나쁠 수 있는가”를 같이 재고, 뒤엣것은 어느 날 틀린 답을 내고 그 원인을 못 찾는다.

실무에서: 되돌아볼 수 없을 때 그리디가 된다

실무 시스템에서 그리디가 나타나는 자리에는 공통점이 있다. 미래를 모르고, 결정을 미룰 수 없을 때다.

• 부하 분산기가 요청을 어느 서버로 보낼지 정할 때, 앞으로 어떤 요청이 올지 모른다. 지금 가장 한가한 서버로 보내는 게 최선이고, 그게 최적이 아닐 수 있다는 건 감수한다.
• 캐시가 무엇을 버릴지 정할 때도 같다. 무엇이 다시 쓰일지 알면 최적으로 버릴 수 있지만 알 수 없으니, “가장 오래 안 쓰인 것”처럼 지금 보이는 정보로 고른다.
• 스케줄러가 다음에 무엇을 돌릴지도 마찬가지다. 남은 작업 시간을 미리 알면 최적 순서가 나오지만, 실제로는 모른다.

그래서 이 자리들에서 나오는 질문은 “왜 최적이 아니냐”가 아니다. **“어떤 상황에서 얼마나 나빠지느냐”**다. 부하 분산이 특정 패턴에서 한 서버로 쏠리거나, 캐시가 한 번씩 훑고 지나가는 작업에 통째로 밀려나는 일이 그 답이다. 그리디의 약점은 성능이 아니라 최악의 경우에 있다.

정리

• 그리디는 매 순간 제일 좋아 보이는 것을 고르고 되돌아보지 않는 것이다. 그래서 빠르고 짧다.
• 빠른 이유와 틀리는 이유가 같다. 되돌아보지 않기 때문이다.
• 일상 경험은 잘못된 확신을 준다. 우리 동전 체계는 그리디가 맞도록 설계되어 있다.
• 맞는지는 짐작으로 알 수 없다. 논리로 보이거나, 작은 입력에서 완전탐색과 맞춰본다.
• 조건이 붙은 그리디를 조심할 것. 음수 간선이 있으면 다익스트라는 틀린다.
• 실무의 그리디는 미래를 모를 때 나온다. 물어야 할 것은 “최적인가”가 아니라 **“최악에 얼마나 나쁜가”**다.

다음 글로 이 시리즈를 닫는다. 지금까지 본 방법들을 한 장에 놓고, 문제를 만났을 때 무엇부터 의심할지를 정리한다.