[2026] 그리디 알고리즘 | 매 순간 최선 탐욕 알고리즘 완벽 정리

들어가며

탐욕법은 구현은 쉬워 보여도 최적성이 맞는지 증명하지 않으면 잘못된 답을 낼 수 있습니다. 이 글에서는 전형적인 그리디 패턴을 익히고, 언제 DP나 다른 전략으로 넘어가야 하는지 감을 잡을 수 있습니다.

”매 순간 최선의 선택이 최적해?”

그리디 알고리즘은 매 순간 최선의 선택을 합니다. 항상 최적해를 보장하지는 않지만, 증명 가능한 경우 매우 효율적입니다.

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

1. 그리디 알고리즘이란?

개념

그리디(탐욕) 알고리즘은 현재 단계에서 보이는 지역 최선만 고릅니다. 아래는 큰 단위 동전부터 최대한 많이 쓰는 거스름돈 예시입니다. 단, 동전 액면가가 임의이면 그리디가 최소 개수를 보장하지 않을 수 있으므로, 문제에서 그리디가 성립하는지(교환·정렬 조건 등)를 확인해야 합니다. 아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 예: 거스름돈 (500, 100, 50, 10원)
# 1260원 거슬러주기
coins = [500, 100, 50, 10]
change = 1260
count = 0
for coin in coins:
    count += change // coin  # 최대한 많이
    change %= coin
print(count)  # 6 (500*2 + 100*2 + 50*1 + 10*1)

그리디 vs DP

특징	그리디	DP
선택	현재 최선	모든 경우 고려
시간복잡도	O(n log n)	O(n²) ~ O(2ⁿ)
최적해 보장	X (증명 필요)	O
구현	간단	복잡

---

2. 대표 문제

문제 1: 회의실 배정

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def max_meetings(meetings):
    """
    최대한 많은 회의 배정
    [(시작, 끝), ...]
    """
    # 끝나는 시간 기준 정렬
    meetings.sort(key=lambda x: x[1])
    
    count = 0
    last_end = 0
    
    for start, end in meetings:
        if start >= last_end:
            count += 1
            last_end = end
    
    return count
# 테스트
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
print(max_meetings(meetings))  # 4
# (1,4), (5,7), (5,9) 선택 불가 → (1,4), (5,7) 선택

문제 2: 동전 거스름돈

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def min_coins(coins, amount):
    """
    최소 동전 개수
    """
    coins.sort(reverse=True)
    count = 0
    
    for coin in coins:
        if amount >= coin:
            count += amount // coin
            amount %= coin
    
    return count if amount == 0 else -1
# 테스트
coins = [500, 100, 50, 10]
print(min_coins(coins, 1260))  # 6
# ❌ 그리디 실패 예
coins = [10, 7, 1]
amount = 14
# 그리디: 10 + 1 + 1 + 1 + 1 = 5개
# 최적: 7 + 7 = 2개 (DP 필요!)

문제 3: 큰 수 만들기

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def make_largest_number(number, k):
    """
    숫자 k개를 제거해서 가장 큰 수 만들기
    "1924", k=2 → "94"
    """
    stack = []
    removed = 0
    
    for digit in number:
        # 스택 top이 현재보다 작으면 제거
        while stack and removed < k and stack[-1] < digit:
            stack.pop()
            removed += 1
        stack.append(digit)
    
    # 아직 k개 안 지웠으면 뒤에서 제거
    return '.join(stack[:len(stack) - (k - removed)])
# 테스트
print(make_largest_number("1924", 2))  # "94"
print(make_largest_number("1231234", 3))  # "3234"

---

3. 그리디 증명

증명 방법

1) 교환 논법 (Exchange Argument)

"그리디 선택을 다른 선택으로 바꿔도 더 나아지지 않음"

2) 귀류법 (Proof by Contradiction)

"그리디가 최적해가 아니라고 가정 → 모순 도출"

예: 회의실 배정 증명

아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

"끝나는 시간이 가장 빠른 회의를 선택하는 것이 최적"
증명:
- 다른 회의를 선택하면 끝나는 시간이 더 늦음
- 끝나는 시간이 늦으면 다음 회의 선택 폭이 줄어듦
- 따라서 끝나는 시간이 빠른 회의가 최적

---

4. 실전 문제

문제 1: 체육복 (프로그래머스)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def solution(n, lost, reserve):
    """
    체육복 빌려주기
    """
    # 여벌 있는데 도난당한 학생 제외
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)
    
    for r in sorted(reserve_set):
        # 앞 번호 학생부터 빌려줌
        if r - 1 in lost_set:
            lost_set.remove(r - 1)
        elif r + 1 in lost_set:
            lost_set.remove(r + 1)
    
    return n - len(lost_set)
# 테스트
print(solution(5, [2, 4], [1, 3, 5]))  # 5

문제 2: 조이스틱 (프로그래머스)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def solution(name):
    """
    조이스틱 최소 이동 횟수
    """
    answer = 0
    min_move = len(name) - 1  # 오른쪽으로만 이동
    
    for i, char in enumerate(name):
        # 상하 이동 (A → char)
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        
        # 좌우 이동 최적화
        next_idx = i + 1
        while next_idx < len(name) and name[next_idx] == 'A':
            next_idx += 1
        
        # 오른쪽 → 왼쪽 vs 왼쪽 → 오른쪽
        min_move = min(
            min_move,
            i + i + len(name) - next_idx,  # 오→왼
            i + len(name) - next_idx + len(name) - next_idx  # 왼→오
        )
    
    return answer + min_move
# 테스트
print(solution("JEROEN"))  # 56

---

실전 팁

그리디 문제 판별법

아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

# ✅ 그리디 신호
# 1. "최대/최소" + 정렬 힌트
# 2. 시간 제한 빡빡 (O(n log n) 필요)
# 3. 반례 찾기 어려움
# ❌ 그리디 불가능
# 1. 반례 존재
# 2. "모든 경우" 고려 필요
# 3. 이전 선택이 영향 (→ DP)

---

정리

핵심 요약

1. 그리디: 매 순간 최선, O(n log n)
2. 증명 필수: 반례 없는지 확인
3. 정렬: 대부분 정렬 후 그리디
4. DP와 비교: 그리디가 더 빠르지만 항상 최적해는 아님

추천 문제

백준:

• 11047번: 동전 0
• 1931번: 회의실 배정
• 11399번: ATM 프로그래머스:
• 체육복
• 조이스틱
• 큰 수 만들기

---

관련 글

• 투 포인터 | O(n²) → O(n) 최적화 기법 완벽 정리
• 알고리즘 시리즈 전체 목차
• 배열과 리스트
• 스택과 큐