그리디(Greedy) 알고리즘

6.1 그리디 알고리즘의 개념

그리디(Greedy) 알고리즘은 매 순간마다 "현재 상황에서 가장 좋아 보이는 선택(최적의 선택)"을 하는 방식으로 전체 문제의 해답을 구하는 알고리즘 설계 기법입니다.

즉, 각 단계에서 지역적으로 최선의 선택을 반복하여, 전체적으로도 최적의 해답에 도달하려는 전략입니다.

특징 및 조건

• 항상 "현재"의 최적 선택이 "전체"의 최적 해(전역 최적해)를 보장하지는 않습니다.
• 하지만 문제의 구조가 "탐욕적 선택 속성(Greedy Choice Property)"과 "최적 부분 구조(Optimal Substructure)"를 만족할 때, 그리디 알고리즘으로도 전체 최적해를 구할 수 있습니다.
• 그리디 알고리즘은 구현이 간단하고, 빠르게 동작(O(n log n) 또는 O(n))하는 경우가 많아 코딩테스트에서 매우 자주 출제됩니다.

대표적인 예시

• 동전 거스름돈 문제
• 회의실 배정 문제
• 최소 신장 트리(프림, 크루스칼)
• 활동 선택 문제
• 배낭 문제(일부 경우)

6.2 대표 문제 및 실습

1. 동전 거스름돈 문제

문제 설명

동전의 종류가 주어졌을 때, 특정 금액을 거슬러 주기 위해 필요한 동전의 최소 개수를 구하시오.

(단, 동전의 종류는 무한히 많음, 각 동전은 1원, 5원, 10원, 50원 등)

• 입력 예시:
• coins = [500, 100, 50, 10] amount = 1260
• 출력 예시:
• 6 # (500x2, 100x2, 50x1, 10x1)

동작 원리

• 가장 큰 동전부터 최대한 많이 사용하여 금액을 줄여나간다.
• 그리디 선택이 항상 최적을 보장하는 이유: 동전 단위가 배수 관계이기 때문(한국 화폐 등).

코드 (Python)

def min_coins(coins, amount):
    """
    가장 큰 동전부터 최대한 많이 사용하여 거스름돈을 만드는 그리디 알고리즘
    """
    count = 0
    coins.sort(reverse=True)  # 큰 단위부터 사용
    for coin in coins:
        if amount == 0:
            break
        use = amount // coin  # 해당 동전 몇 개 사용 가능한지
        count += use
        amount -= coin * use  # 남은 금액 갱신
        # print(f"{coin}원 동전 {use}개 사용, 남은 금액: {amount}")
    return count

# 예시 실행
coins = [500, 100, 50, 10]
amount = 1260
print(min_coins(coins, amount))  # 6

2. 회의실 배정 문제 (활동 선택 문제)

문제 설명

N개의 회의에 대해 각 회의의 시작 시간과 끝나는 시간이 주어질 때, 한 회의실에서 겹치지 않게 최대한 많은 회의를 할 수 있는 최대 개수를 구하시오.

• 입력 예시:
• meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
• 출력 예시:
• text4

동작 원리

• 끝나는 시간이 가장 빠른 회의부터 선택한다.
• 이미 선택한 회의와 겹치지 않는 회의만 선택.
• 그리디 선택이 전체 최적을 보장: "가장 빨리 끝나는 회의"를 선택하면 남은 시간에 더 많은 회의를 배치할 수 있기 때문.

코드 (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
            # print(f"회의 선택: 시작={start}, 종료={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(max_meetings(meetings))  # 4

3. 기타: 가장 큰 수 만들기 (자주 출제되는 유형)

문제 설명

N개의 숫자 카드에서 K번만 한 장을 골라 숫자를 만들 때, 만들 수 있는 가장 큰 수를 구하시오.

• 입력 예시:
• numbers = [3, 30, 34, 5, 9]
• 출력 예시:
• 9534330

동작 원리

• 두 수를 이어붙였을 때 더 큰 조합이 앞으로 오도록 정렬.
• 문자열 비교를 활용한 그리디.

코드 (Python)

from functools import cmp_to_key

def compare(x, y):
    # x+y와 y+x 중 더 큰 쪽이 앞으로 오도록 정렬
    return (int(y + x) > int(x + y)) - (int(y + x) < int(x + y))

def largest_number(numbers):
    """
    숫자들을 이어붙여 만들 수 있는 가장 큰 수를 구하는 그리디 알고리즘
    """
    numbers = list(map(str, numbers))
    numbers.sort(key=cmp_to_key(compare))
    result = ''.join(numbers)
    # 0으로 시작하는 경우(모두 0) 처리
    return result if result[0] != '0' else '0'

# 예시 실행
numbers = [3, 30, 34, 5, 9]
print(largest_number(numbers))  # '9534330'