그리디(Greedy) 알고리즘

용인사는 개발자·2026년 3월 3일

목록 보기

3/3

들어가기전에

알고리즘 문제를 풀다 보면 처음엔 DP나 이분탐색처럼 뭔가 거창한 로직이 필요할 것 같았는데, 의외로 지금 당장 가장 좋은 선택을 하는 것만으로 풀리는 문제들도 꽤 많았다.
이런 유형이 바로 그리디(Greedy) 이다.

처음에는 나도 그리디를 보면 좀 애매했다.
이게 진짜 맞는 선택인가? 지금 최선이 나중에도 최선이 맞나?
이런 생각 때문에 오히려 어렵게 느껴졌다.

이번 글에서는 코딩 테스트에서 자주 등장하는 그리디 패턴이 어떤 느낌인지, 그리고 어떤 문제에서 떠올려야 하는지를 예시와 함께 정리해보려고 한다.

그리디란?

정말 단순하다. 그리디는 상남자처럼 매 순간 가장 좋아 보이는 선택을 하는 방식이다.

즉,

지금 당장 이득이 가장 큰 선택을 하고
그 선택을 계속 이어가며 최종 답을 만드는 방식

핵심은 매 선택이 미래까지 포함해서도 문제를 깨지 않아야 한다는 점이다.
그래서 모든 문제를 그리디로 풀 수 있는 건 아니고,
지금의 최선이 전체 최선으로 이어지는 구조 가 있어야 한다.

왜 그리디가 어려운가?

그리디는 구현 자체는 단순한 경우가 많다.
근데 어려운 건 구현이 아니라 이 문제를 그리디로 봐도 되는지 판단하는 것이다.

예를 들어,

당장 가장 커 보이는 값을 고른다
당장 가장 빨리 끝나는 걸 고른다
당장 가장 작은 비용을 선택

이런 선택이 항상 정답이 되는 건 아니다.

그래서 그리디 문제는 보통
왜 이 선택이 맞는가? 를 한 번 납득해야 한다.

예제로 살펴보기

이번에도 LeetCode 예제로 정리해보려고 한다.
그리디는 문제를 많이 볼수록 아 이런느낌인가? 하고 감이 오는 것 같다.

Assign Cookies (Easy)

문제) 아이들의 만족도와 쿠키 크기가 주어질 때, 최대 몇 명의 아이를 만족시킬 수 있는지 구하라.

예를 들어
아이의 만족도: [1,2,3]
쿠키 크기: [1,1]

라면, 만족도 1인 아이만 만족시킬 수 있으니 정답은 1 이다.

// 가장 작은 아이부터, 줄 수 있는 가장 작은 쿠키를 준다.
var findContentChildren = function(g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);

    let i = 0; // child
    let j = 0; // cookie

    while (i < g.length && j < s.length) {
        if (s[j] >= g[i]) {
            i++;
        }
        j++;
    }

    return i;
};

이 문제는 그리디의 대표적인 느낌이 잘 보인다.
가장 만족도가 작은 아이부터 처리하고, 그 아이를 만족시킬 수 있는 가장 작은 쿠키를 주는 게 핵심이다.

처음엔 큰 쿠키를 먼저 쓰면 안 되나? 싶었는데,
그러면 작은 아이한테 큰 쿠키를 낭비할 수 있어서 오히려 손해였다.

즉, 작은 요구는 작은 자원으로 해결하는 게 이득 이다.

Best Time to Buy and Sell Stock II (Medium)

문제) 주식 가격이 주어질 때, 여러 번 거래할 수 있다면 얻을 수 있는 최대 이익을 구하라.

// 오를 때마다 그 차익을 모두 더하면 된다.
var maxProfit = function(prices) {
    let profit = 0;

    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }

    return profit;
};

이 문제도 처음 보면
언제 사고 언제 팔아야 최대지? 하면서 어렵게 생각하게 된다.

근데 잘 보면
1 -> 3 -> 5 처럼 계속 오르는 구간은
결국 5 - 1 이익과
(3 - 1) + (5 - 3) 이익이 같다.

그래서 오르는 구간의 이익을 전부 더해도 최종 최대 이익과 같다.

이 문제를 풀면서 느낀 건,
그리디는 가끔 문제를 쪼개서 생각하면 갑자기 쉬워진다는 점이다.
한 번의 완벽한 거래를 찾으려 하지 말고,
그냥 지금 오르면 먹는다 라고 보면 된다.

Jump Game (Medium)

문제) 배열의 각 원소는 현재 위치에서 점프할 수 있는 최대 거리일 때, 마지막 인덱스까지 도달 가능한지 판단하라.

// 지금까지 도달 가능한 가장 먼 위치만 관리
var canJump = function(nums) {
    let farthest = 0;

    for (let i = 0; i < nums.length; i++) {
        if (i > farthest) return false;
        farthest = Math.max(farthest, i + nums[i]);
    }

    return true;
};

이 문제는 처음에 나도 DFS나 DP 느낌으로 생각할 수 있을 것 같았는데,
막상 핵심은 단순했다.

현재 위치까지 올 수 있다면, 여기서 갈 수 있는 가장 먼 위치를 계속 갱신하면 된다.

즉,

지금 인덱스가 이미 도달 불가능한 위치면 실패
아니면 i + nums[i] 로 갈 수 있는 범위를 계속 늘린다

이 문제를 보고 나서 그리디의 느낌이 조금 더 명확해졌다.
모든 경로를 다 볼 필요 없이,
지금까지 만들 수 있는 최선의 범위 만 추적하면 되는 경우가 있다.

그리디 문제를 언제 떠올려야 하는가?

다음과 같은 느낌이 보이면 그리디를 의심해볼 수 있다.

최대한 많은 개수
최소 횟수 / 최소 비용
지금 선택이 이후 선택에 영향을 주는 구조
정렬 후 앞에서부터 처리
현재 상태에서 가장 이득인 선택

특히 이런 문제들이 많다.

회의실 배정
구간 선택
주유소 / 점프 / 배정 문제
동전 문제(일부 조건에서만)
정렬 후 순서대로 결정하는 문제

그리디 문제를 많이 풀다 보면
정렬 + 순차 처리 조합이 진짜 자주 나온다는 걸 느끼게 된다.

그리디의 핵심은?

내가 느낀 그리디의 핵심은 이거였다.

지금 당장 최선처럼 보이는 선택을 해도, 나중에 후회하지 않는가?

이걸 확인할 수 있으면 그리디고,
그걸 확신할 수 없으면 보통 DP나 다른 접근을 봐야 한다.

그래서 그리디는 막연히 대충 좋아 보이는 거 고르는 것 이 아니라,
근거 있게 포기하고, 근거 있게 선택하는 방식 에 가깝다.

마무리

그리디는 처음엔 쉬워 보이는데 오히려 그래서 더 헷갈렸다.
구현은 짧은데, 왜 이게 정답이지? 를 설명하려고 하면 막히는 경우가 많았다.

특히 나 같은 경우는 문제를 보면 괜히 복잡하게 생각하는 습관이 있어서,
그리디 문제도 처음엔 DP처럼 보려고 했던 적이 많았다.
근데 몇 문제 풀어보니 정렬하고, 지금 가능한 최선의 선택을 쌓아간다
이 흐름이 보이기 시작했다.

아직도 낯선 문제를 보면 바로 그리디라고 확신하긴 어렵지만,
적어도 이제는 이거 혹시 정렬하고 앞에서부터 처리하는 문제 아닌가?
정도는 먼저 떠올려보게 된 것 같다.

역시 알고리즘은 많이 틀려보고,
왜 틀렸는지 정리하면서 익숙해지는 게 제일 중요한 것 같다.
많이 풀어봤어도 아직도 많이 어렵다 ㅋㅋ;

용인사는 개발자

용인에 거주하는 개발자입니다. 사이드프로젝트의 진행사항, 오류해결, 배운것들을 적습니다

이전 포스트