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

그리디(Greedy) 알고리즘은 매 순간 최선의 선택을 하는 알고리즘입니다. 현재 상황에서 가장 좋아 보이는 선택을 반복하여 최종 해답에 도달합니다.

1.1 그리디 알고리즘의 특징

• 지역 최적해(Local Optimum): 각 단계에서 최선의 선택
• 되돌아가지 않음: 한 번 선택하면 번복하지 않음
• 빠른 속도: 대부분 O(n) 또는 O(n log n)
• 최적해 보장 안 됨: 항상 최적해를 보장하지는 않음

1.2 그리디 vs 다른 알고리즘

2. 그리디 알고리즘 기본 패턴

2.1 정렬 후 그리디

많은 그리디 문제는 정렬 후에 순서대로 선택하는 패턴을 따릅니다.

# 패턴: 정렬 → 순서대로 선택
def greedy_with_sort(items):
    items.sort()  # 또는 key 기준으로 정렬
    result = 0

    for item in items:
        # 조건에 맞으면 선택
        if can_select(item):
            result += item  # 또는 다른 처리

    return result

2.2 가장 큰/작은 값 선택

현재 상황에서 가장 크거나 작은 값을 선택하는 패턴입니다.

# 패턴: 매번 최대/최소 선택
def greedy_select_extreme(items):
    result = []

    while items:
        # 가장 큰 값 선택
        max_item = max(items)
        result.append(max_item)
        items.remove(max_item)

        # 또는 heapq 사용
        # import heapq
        # max_item = -heapq.heappop(items)

    return result

3. 그리디 대표 문제

3.1 거스름돈 문제

가장 대표적인 그리디 문제로, 가장 큰 단위부터 거슬러 줍니다.

def min_coins(change):
    """
    거스름돈을 최소 동전 개수로 반환
    (동전: 500, 100, 50, 10원)
    """
    coins = [500, 100, 50, 10]
    count = 0

    for coin in coins:
        count += change // coin  # 해당 동전으로 거슬러 줄 수 있는 개수
        change %= coin           # 남은 금액

    return count

print(min_coins(1260))  # 6 (500*2 + 100*2 + 50*1 + 10*1)
print(min_coins(3780))  # 11

3.2 물품 대여 문제

def lend_items(n, broken, spare):
    """
    n명의 사원이 있고, 일부 사원은 장비가 고장났습니다(broken).
    여분의 장비를 가진 사원(spare)은 자신의 바로 앞이나 뒤 번호의
    사원에게만 장비를 빌려줄 수 있습니다.
    여분이 있어도 자신의 장비가 고장나면 빌려줄 수 없습니다.
    업무를 수행할 수 있는 최대 사원 수를 반환하세요.
    """
    # 여분이 있지만 본인 장비가 고장난 사원 제외
    spare_set = set(spare) - set(broken)
    broken_set = set(broken) - set(spare)

    # 앞 번호부터 빌려주기 (그리디)
    for s in sorted(spare_set):
        # 앞 번호 먼저 확인 (작은 번호 우선)
        if s - 1 in broken_set:
            broken_set.remove(s - 1)
        elif s + 1 in broken_set:
            broken_set.remove(s + 1)

    # 전체 사원 - 장비 없는 사원
    return n - len(broken_set)

print(lend_items(5, [2, 4], [1, 3, 5]))  # 5
print(lend_items(5, [2, 4], [3]))        # 4

3.3 숫자 제거하여 최댓값 만들기

def make_largest_number(number, k):
    """
    숫자 문자열에서 k개의 숫자를 제거하여 가장 큰 수를 만듭니다.
    순서는 유지해야 합니다.

    예: "1924"에서 2개 제거 → "94" (1, 2 제거)
    """
    stack = []
    remove_count = 0

    for digit in number:
        # 스택 top보다 현재 숫자가 크면 제거
        while stack and remove_count < k and stack[-1] < digit:
            stack.pop()
            remove_count += 1

        stack.append(digit)

    # 아직 제거할 개수가 남았으면 뒤에서 제거
    if remove_count < k:
        stack = stack[:-(k - remove_count)]

    return ''.join(stack)

print(make_largest_number("1924", 2))       # "94"
print(make_largest_number("1231234", 3))    # "3234"
print(make_largest_number("4177252841", 4)) # "775841"

3.4 문자열 조작 최소 비용

def min_operations(target):
    """
    초기 문자열 "AAA...A"에서 목표 문자열을 만들기 위한 최소 조작 횟수

    조작 규칙:
    - 위/아래: 현재 위치의 문자를 다음/이전 알파벳으로 변경 (A→B 또는 A→Z)
    - 좌/우: 커서를 이동

    커서는 처음에 맨 왼쪽에 있습니다.
    """
    # 각 문자를 만들기 위한 최소 조작 횟수
    def char_cost(c):
        # A에서 시작, 위로 가거나 Z에서 아래로 가기
        return min(ord(c) - ord('A'), ord('Z') - ord(c) + 1)

    n = len(target)

    # 모든 문자 변경 비용
    total = sum(char_cost(c) for c in target)

    # 커서 이동 최소 비용 (기본: 오른쪽으로 쭉)
    min_move = n - 1

    for i in range(n):
        # i 위치에서 연속된 A의 끝 찾기
        next_i = i + 1
        while next_i < n and target[next_i] == 'A':
            next_i += 1

        # 왼쪽으로 갔다가 오른쪽으로, 또는 오른쪽으로 갔다가 왼쪽으로
        # 1. 오른쪽으로 i까지 갔다가 돌아와서 왼쪽 끝으로
        move1 = i + i + (n - next_i)
        # 2. 왼쪽으로 (n - next_i)만큼 갔다가 돌아와서 오른쪽으로
        move2 = (n - next_i) * 2 + i

        min_move = min(min_move, move1, move2)

    return total + min_move

print(min_operations("JEROEN"))  # 56
print(min_operations("JAN"))     # 23

3.5 택시 최소 배차

def min_taxis(weights, limit):
    """
    여러 사람이 택시를 타려고 합니다.
    한 택시에는 최대 2명까지 탈 수 있고, 무게 제한이 있습니다.
    필요한 최소 택시 수를 반환하세요.

    weights: 각 사람의 무게 리스트
    limit: 택시 무게 제한
    """
    weights.sort()  # 무게 순 정렬

    count = 0
    left, right = 0, len(weights) - 1

    while left <= right:
        # 가장 무거운 사람은 무조건 태움
        # 가장 가벼운 사람과 함께 탈 수 있는지 확인
        if weights[left] + weights[right] <= limit:
            left += 1  # 가벼운 사람도 태움

        right -= 1  # 무거운 사람 태움
        count += 1

    return count

print(min_taxis([70, 50, 80, 50], 100))  # 3
print(min_taxis([70, 80, 50], 100))      # 3

3.6 회의실 최대 배정

def meeting_room(meetings):
    """
    회의실에서 최대 몇 개의 회의를 할 수 있는지
    meetings: [(시작시간, 종료시간), ...]
    """
    # 종료 시간 기준 정렬 (핵심!)
    meetings.sort(key=lambda x: (x[1], x[0]))

    count = 0
    end_time = 0

    for start, end in meetings:
        # 이전 회의가 끝난 후에 시작하는 회의만 선택
        if start >= end_time:
            count += 1
            end_time = end

    return count

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
print(meeting_room(meetings))  # 4

4. 그리디 문제 접근법

4.1 그리디 문제 판별

4.2 그리디 체크리스트

1. 정렬 기준 찾기: 어떤 기준으로 정렬해야 하는가?
2. 선택 기준 찾기: 매번 무엇을 기준으로 선택하는가?
3. 반례 확인: 그리디가 최적해를 보장하는가?
4. 구현: 정렬 후 순차 처리

5. 흔한 그리디 패턴

5.1 가장 작은 것 먼저

# 예: 최소 동전 개수
# 예: 최소 회의 시간으로 최대 회의 수

items.sort()  # 오름차순
for item in items:
    if can_select(item):
        select(item)

5.2 가장 큰 것 먼저

# 예: 가장 큰 수 만들기
# 예: 최대 이익

items.sort(reverse=True)  # 내림차순
for item in items:
    if can_select(item):
        select(item)

5.3 종료 시간 기준 정렬

# 예: 회의실 배정
# 예: 작업 스케줄링

intervals.sort(key=lambda x: x[1])  # 종료 시간 기준
for start, end in intervals:
    if start >= last_end:
        select()
        last_end = end

5.4 양 끝에서 접근

# 예: 구명보트
# 예: 두 수의 합

items.sort()
left, right = 0, len(items) - 1
while left <= right:
    # 양 끝의 값을 활용
    process(items[left], items[right])

6. 연습문제

• (그리디) 비행정 탑승: https://pyalgo.co.kr/?page=13
• (그리디) 리치: https://pyalgo.co.kr/?page=19
• (그리디) 빙키: https://pyalgo.co.kr/?page=20
• (그리디) 최소 동전: https://100.pyalgo.co.kr/?page=51
• (그리디) 잔돈: https://100.pyalgo.co.kr/?page=52