욕심쟁이 알고리즘(Greedy Algorithm)

in Blog / 알고리즘

순간 순간 가장 좋아 보이는 선택을 하면 정말 좋겠지? 인생에서 그러기 쉽지 않지만, 그런 특성을 가진 알고리즘이 그리디 알고리즘이야.

Greedy 알고리즘 핵심 개념

그리디 알고리즘은 아래 두 가지 조건이 충족될 때 사용할 수 있어

  • 탐욕 선택 속성(Greedy Choice Property) : 현재 순간의 최선의 선택이 결국 전체에서도 최선의 해의 일부여야 해

→ 회의실 배정 문제에서 종료 시간이 가장 빠른 회의를 먼저 선택해도, 결과적으로 전체 최적해에 포함될 수 있음

  • 최적 부분 구조(Optimal Substructure) : 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 해

→ 전체 일정 중 일부 회의를 잘 선택하면, 남은 회의 일정에서도 그리디하게 선택해도 무방

정렬이 핵심이다

그리디 알고리즘에서는 대부분 정렬을 먼저 하고, 그 다음 루프를 돌면서 선택하는 방식이 많아

  • 회의실 문제 → 종료 시간 기준 정렬

  • 동전 문제 → 금액 기준 내림차순 정렬

  • 작업 스케줄링 문제 → 보상/시간 효율 정렬

다이나믹 프로그래밍(DP)과 헷갈리면 비교해보자

구분그리디다이나믹 프로그래밍
접근현재 최선 선택모든 경우 고려
시간복잡도대체로 빠름느릴 수 있음 (메모이제이션으로 개선 가능)
필요조건탐욕 선택 속성, 최적 부분 구조최적 부분 구조
예시동전 거스름돈, 회의실 배정피보나치, 배낭 문제(0/1 knapsack)

※ 배낭 문제 같은 경우는 “무게 제한이 있을 때 최대로 담는 것”인데, 가벼운 거부터 담자라는 그리디 방식은 틀릴 수도 있어 → 이건 DP가 더 적합한 문제.

반례를 생각하라

그리디로 풀고 싶을 때 항상 “이 방법이 틀릴 수도 있는 케이스가 있을까?”를 생각해야 해

예를 들어 동전 문제에서 [500, 400, 100]으로 800원을 거슬러준다면? → 500 + 100 + 100 + 100 (총 4개) → ❌ → 400 + 400 (총 2개) → ✅ → 그리디로는 못 풀어!

예제(회의실 배정 문제)

문제 설명

  • 회의는 시작 시간과 끝나는 시간이 주어져

  • 회의가 겹치지 않게 하면서, 가장 많은 회의를 배정하는 게 목표야

그리디 전략

  • 끝나는 시간이 가장 빠른 회의부터 선택한다. → 이후 회의가 들어갈 수 있는 여지를 최대한 남기는 전략
# 회의 리스트 (시작시간, 종료시간)
meetings = [
    (1, 4),
    (3, 5),
    (0, 6),
    (5, 7),
    (3, 9),
    (5, 9),
    (6, 10),
    (8, 11),
    (8, 12),
    (2, 14),
    (12, 16)
]

# 1. 종료 시간 기준으로 정렬
meetings.sort(key=lambda x: x[1])

# 2. 그리디 선택
count = 0
last_end = 0

for start, end in meetings:
    if start >= last_end:  # 회의가 겹치지 않으면 선택
        count += 1
        last_end = end

print("최대 선택 가능한 회의 수:", count)

핵심 포인트

meetings.sort(key=lambda x: x[1]) → 종료 시간 기준 정렬!

  • 조건: start >= last_end → 이전 회의 끝난 이후에 시작해야 선택 가능

  • 그리디한 선택을 반복하며 최적해 도출

마무리 정리

  • 빠르게 동작하며, 구현이 간단함

© 2022 JeongHwan Yun.