[WEEK04] 그리디 알고리즘

그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은 현재 상황에서 가장 최선의 선택(탐욕적인 선택, Greedy Choice)을 하는 방식으로 최적해를 구하는 알고리즘이다. 즉, 한 단계씩 최적의 선택을 하면서 전체 문제의 최적해를 찾아가는 방식이다.

그리디 알고리즘이 등장한 이유

컴퓨터 과학에서 다양한 문제를 해결할 때, 효율적인 알고리즘이 필요하다. 특히, 조합 최적화 문제(Combinatorial Optimization)에서 빠른 시간 내에 해를 구하는 것이 중요한 경우가 많다.

 

동적 계획법(Dynamic Programming)이나 백트래킹(Backtracking) 같은 방식은 최적해를 찾을 수 있지만, 계산량이 많아 시간이 오래 걸릴 수 있다. 그리디 알고리즘은 계산량을 줄이고 빠르게 근사 최적해를 구하기 위해 등장하게 되었다.

왜 그리디 알고리즘을 사용해야 하는가?

그리디 알고리즘을 사용할 수 있는 이유는 다음과 같다.

• 빠른 계산 속도: 매 단계에서 최선의 선택을 하므로 연산이 빠르다.
• 직관적인 접근법: 문제를 해결하는 방식이 직관적이며 구현하기 쉽다.
• 특정 문제에서 최적해 보장: 탐욕적 선택 속성이 성립하면 최적해를 보장한다.
• 공간 복잡도 절약: 동적 계획법과 달리 추가적인 메모리를 많이 사용하지 않는다.

하지만 모든 문제에서 항상 최적해를 보장하는 것은 아니다. 그리디 알고리즘을 적용하려면 탐욕적 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optimal Substructure)를 만족하는지 확인해야 한다.

• 탐욕스런 선택 조건 (Greedy Choice Property) : 현재의 선택이 미래의 선택에 영향을 주지 않을 경우
• 최적 부분 구조 조건 (Optimal Substructure) : 부분의 최적 해가 모이면 전체의 최적 해가 되는 경우

그리디 알고리즘 수행 과정

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

그리디 알고리즘의 대표적인 예제

(1) 동전 거스름돈 문제

문제: 손님에게 거스름돈을 줄 때, 가장 적은 개수의 동전을 사용하는 방법을 구하시오.

해결 방법: 가장 큰 동전부터 사용하면 최적해를 구할 수 있다. (단, 동전 단위가 적절해야 한다.)

# 동전 거스름돈 문제 (그리디 알고리즘 적용)
def min_coins(change, coins):
    coins.sort(reverse=True)  # 큰 동전부터 정렬
    count = 0
    
    for coin in coins:
        count += change // coin  # 해당 동전으로 거슬러 줄 수 있는 개수 계산
        change %= coin  # 남은 거스름돈 계산
    
    return count

# 테스트
coins = [500, 100, 50, 10]
change = 1260
print(min_coins(change, coins))  # 출력: 6

(2) 활동 선택 문제(Activity Selection Problem)

문제: 여러 개의 회의가 주어졌을 때, 겹치지 않으면서 가장 많은 회의를 선택하는 방법을 찾으시오.

해결 방법: 회의 종료 시간이 빠른 순서대로 선택하면 최적해를 보장할 수 있다.

# 활동 선택 문제 (그리디 알고리즘 적용)
def max_activities(activities):
    activities.sort(key=lambda x: x[1])  # 종료 시간을 기준으로 정렬
    
    selected = []
    last_end_time = 0
    
    for start, end in activities:
        if start >= last_end_time:
            selected.append((start, end))
            last_end_time = end
    
    return selected

# 테스트
activities = [(1, 3), (2, 5), (3, 9), (6, 8), (5, 7)]
print(max_activities(activities))  # [(1, 3), (5, 7), (6, 8)]

그리디 알고리즘의 한계

그리디 알고리즘은 항상 최적해를 보장하는 것은 아니다. 예를 들어, 배낭 문제(Knapsack Problem)에서 단순히 가장 가치가 높은 물건부터 선택하면 최적해를 구할 수 없다. 이러한 경우에는 동적 계획법(Dynamic Programming)이나 백트래킹(Backtracking)을 고려해야 한다.

정리

그리디 알고리즘은 빠르고 직관적인 방법으로 최적해를 찾거나 근사해를 구할 수 있다. 하지만 모든 문제에서 적용 가능한 것은 아니므로, 탐욕적 선택 속성과 최적 부분 구조를 만족하는지 항상 확인해야 한다. 다양한 문제를 풀어보면서 그리디 알고리즘을 적용할 수 있는 상황을 익히는 것이 중요하다.