[과제] Greedy 알고리즘

1. Greedy 알고리즘이란?

1.1 Greedy 알고리즘의 의미

Greedy 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 반복해서 문제를 해결하는 알고리즘이다.

전체 경우를 모두 비교하지 않고, 매 순간 가장 이득이 되는 선택을 한다.

예를 들어 거스름돈을 줄 때 가장 큰 동전부터 사용하는 방법이 greddy 방식이다.

500원, 100원, 50원, 10원 동전이 있을 때 760원을 거슬러 준다면 500원부터 먼저 선택하는 식이다.

1.2 동작 방식

1. 현재 상황에서 선택할 수 있는 후보들을 확인한다.
2. 그중 가장 좋아 보이는 선택을 고른다.
3. 선택한 결과를 문제에 반영한다.
4. 문제가 끝날 때까지 위 과정을 반복한다.
5. 최종 결과를 출력한다

1.3 특징

• 매 순간 가장 좋아 보이는 선택을 한다.
• 선택한 결과를 되돌리지 않는다.
• 구현이 비교적 간단하다.
• 모든 문제에서 항상 최적의 정답을 보장하지는 않는다.
• 문제에 따라 정렬을 먼저 사용하는 경우가 많다.

1.4 조건

greedy 알고리즘이 항상 최적의 답을 만들려면 다음 성질이 필요하다.

조건	설명
탐욕 선택 속성	현재의 최선 선택이 전체 문제의 최적해로 이어져야 한다.
최적 부분 구조	부분 문제의 최적해를 모으면 전체 문제의 최적해가 되어야 한다.

1.5 장점

• 구현이 단순하고 이해하기 쉽다.
• 실행 속도가 빠른 경우가 많다.
• 복잡한 완전 탐색보다 효율적으로 문제를 해결할 수 있다.
• 정렬과 반복문만으로 해결되는 문제가 많다.

1.6 단점

• 항상 최적의 정답을 보장하지 않는다.
• 현재 선택이 나중에 나쁜 결과로 이어질 수 있다.
• greedy로 풀 수 있는 문제인지 판단하는 과정이 중요하다.
• 문제 조건이 조금만 바껴도 잘못된 답이 나올 수 있다.

1.7 사용하는 상황

• 현재의 최선 선택이 전체 최선 결과로 이어지는 경우
• 정렬 후 순서대로 선택하면 답을 만들 수 있는 경우
• 빠른 판단이 필요한 경우
• 모든 경우를 탐색하기에는 경우의 수가 너무 많은 경우

2. Greedy Algorithm 문제

2.1 거스름돈 문제

문제 설명

거스름돈 금액이 주어졌을 때, 동전의 개수가 가장 적게 나오도록 거스름돈을 계산하는 문제이다.

동작 원리

1. 동전을 큰 금액부터 정렬한다.
2. 현재 금액에서 사용할 수 있는 가장 큰 동전을 선택한다.
3. 해당 동전을 몇 개 사용할 수 있는지 계산한다.
4. 남은 금액을 다시 계산한다.
5. 남은 금액이 0이 될 때까지 반복한다.

Python 구현

def coin_change(amount, coins):
    result = {}
    total_count = 0

    # 큰 동전부터 사용하기 위해 내림차순 정렬
    coins.sort(reverse=True)

    for coin in coins:
        # 현재 동전을 몇 개 사용할 수 있는지 계산
        count = amount // coin

        if count > 0:
            result[coin] = count
            total_count += count
            amount %= coin

    return result, total_count


coins = [500, 100, 50, 10]
amount = 760

change, total_count = coin_change(amount, coins)

print(f"거스름돈: {amount}원")
print(f"동전 개수: {total_count}개")

for coin, count in change.items():
    print(f"{coin}원: {count}개")

실행 결과

거스름돈: 760원
동전 개수: 5개
500원: 1개
100원: 2개
50원: 1개
10원: 1개

2.2 회의실 배정 문제

문제 설명

여러 개의 회의 시간이 주어졌을 때, 한 회의실에서 최대한 많은 회의를 진행할 수 있도록 회의르르 선택하는 문제이다.

회의는 시작 시간과 종료 시간이 있으며, 하나의 회의가 끝난 뒤에 다음 회의를 진행할 수 있다.

동작 원리

1. 회의를 종료 시간이 빠른 순서대로 정렬한다.
2. 종료 시간이 같다면 시작 시간이 빠른 순서대로 정렬한다.
3. 현재 선택한 회의의 종료 시간보다 시작 시간이 같거나 늦은 회의를 선택한다.
4. 선택한 회의의 종료 시간을 기준으로 다음 회의를 찾는다.
5. 더 이상 선택할 수 있는 회의가 없을 때까지 반복한다.

python 구현

def assign_meetings(meetings):
    selected = []
    end_time = 0

    meetings.sort(key=lambda meeting: (meeting[1], meeting[0]))

    for start, end, title in meetings:
        if start >= end_time:
            selected.append((start, end, title))
            end_time = end

    return selected


meetings = [
    (1, 4, "자료구조 스터디"),
    (3, 5, "알고리즘 풀이"),
    (0, 6, "프로젝트 회의"),
    (5, 7, "Python 복습"),
    (3, 8, "DB 설계"),
    (5, 9, "코드 리뷰"),
    (6, 10, "면접 준비"),
    (8, 11, "Git 특강"),
    (8, 12, "웹 기초"),
    (12, 14, "최종 정리")
]

selected_meetings = assign_meetings(meetings)

print(f"배정 가능한 회의 수: {len(selected_meetings)}개")

for start, end, title in selected_meetings:
    print(f"{start}시 ~ {end}시: {title}")

실행 결과

배정 가능한 회의 수: 4개
1시 ~ 4시: 자료구조 스터디
5시 ~ 7시: Python 복습
8시 ~ 11시: Git 특강
12시 ~ 14시: 최종 정리

2.3 배낭 문제

문제 설명

배낭 문제는 정래진 무게만 담을 수 있는 배낭에 물건을 넣어 최대한 높은 가치를 얻는 문제이다.

greedy 알고리즘으로 풀기 좋은 대표적인 배낭 문제는 분할 가능한 배낭 문제(Fractional Knapsack Problem)이다. 이 문제에서는 물건을 쪼개서 넣을 수 있다.

예를 들어 쌀, 금가루, 밀가루처럼 물건을 일부만 담을 수 있다면 가치가 높은 비율대로 담는 greedy 알고리즘을 사용할 수 있다.

동작원리

1. 각 물건의 무게 대비 가치를 계산한다.
2. 무게 대비 가치가 높은 순서대로 정렬한다.
3. 배낭에 넣을 수 있으면 물건 전체를 넣는다.
4. 물건 전체를 넣을 수 없다면 남은 무게만큼 일부만 넣는다.
5. 배낭이 가득 찰 때까지 반복한다.

python 구현

def fractional_knapsack(capacity, items):
    total_value = 0
    selected_items = []

    items.sort(key=lambda item: item["value"] / item["weight"], reverse=True)

    for item in items:
        if capacity == 0:
            break

        name = item["name"]
        weight = item["weight"]
        value = item["value"]

        if weight <= capacity:
            selected_items.append((name, weight, value, 100))
            total_value += value
            capacity -= weight
        else:
            ratio = capacity / weight
            partial_value = value * ratio
            selected_items.append((name, capacity, partial_value, ratio * 100))
            total_value += partial_value
            capacity = 0

    return selected_items, total_value


items = [
    {"name": "노트북", "weight": 3, "value": 600},
    {"name": "카메라", "weight": 2, "value": 500},
    {"name": "책", "weight": 4, "value": 300},
    {"name": "이어폰", "weight": 1, "value": 150}
]

capacity = 5

selected_items, total_value = fractional_knapsack(capacity, items)

print(f"배낭 최대 무게: {capacity}kg")
print(f"총 가치: {total_value:.1f}")

for name, weight, value, percent in selected_items:
    print(f"{name}: {weight}kg, 가치 {value:.1f}, 사용 비율 {percent:.1f}%")

실행 결과

배낭 최대 무게: 5kg
총 가치: 1100.0
카메라: 2kg, 가치 500.0, 사용 비율 100.0%
노트북: 3kg, 가치 600.0, 사용 비율 100.0%

3. 세 문제 비교

문제	그리디 선택 기준	정렬 기준	핵심 아이디어
거스름돈 문제	가장 큰 동전부터 선택	동전 금액 내림차순	큰 단위부터 사용해서 동전 수 줄이기
회의실 배정 문제	가장 빨리 끝나는 회의 선택	종료 시간 오름차순	남은 시간을 최대한 많이 확보하기
분할 가능한 배낭 문제	무게 대비 가치가 높은 물건 선택	가치 / 무게 내림차순	같은 무게에서 더 큰 가치를 얻기

정리

그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 반복하는 알고리즘이다.
구현이 간단하고 빠르다는 장점이 있지만, 모든 문제에서 최적의 답을 보장하지는 않는다.

따라서 그리디 알고리즘을 사용할 때는 현재의 최선 선택이 전체 문제의 최적해로 이어지는지 확인해야 한다.
거스름돈 문제, 회의실 배정 문제, 분할 가능한 배낭 문제처럼 그리디 선택이 최적해로 이어지는 문제에서는 매우 효율적으로 사용할 수 있다.