Greedy Algorithm(그리디 알고리즘)

✅ Greedy 알고리즘 (Greedy Algorithm)

그리디 알고리즘과 최적의 선택 차이

 

Greedy 알고리즘은 매 단계에서 현재 상황에서 가장 좋아 보이는 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다. 즉, 국소 최적해(local optimum)를 구하는 방식으로, 이를 통해 전체 최적해(global optimum)를 찾고자 합니다. Greedy 알고리즘은 직관적이고 빠르게 구현할 수 있지만, 모든 문제에 대해 최적의 해를 보장하지는 않습니다. 하지만 특정 유형의 문제에서는 매우 효율적이고 정확한 결과를 낼 수 있습니다.

 

항목	내용
알고리즘 정의	각 단계에서 가장 좋은 선택을 하여 문제를 해결하는 방식
특징	1. 직관적이고 간단한 구현 2. 최적해 보장 안 됨 3. 빠른 실행 속도
시간 복잡도	보통 O(n log n) 또는 O(n) 정도
적합한 경우	최적의 해가 항상 지역 최적해에서 도출되는 문제
단점	최적해를 보장하지 않음, 일부 문제에서는 잘못된 결과를 낼 수 있음
예시	동전 거스름돈 문제, 최소 신장 트리(MST) 문제

 

✅ 특징

• 직관적이고 간단한 구현: 각 단계에서 가장 좋은 선택을 하는 방식으로 문제를 해결하기 때문에 알고리즘이 간단하고 이해하기 쉽습니다.
• 최적해 보장 안 됨: 일부 문제에서는 국소 최적해가 전체 최적해를 보장하지 않기 때문에 최적의 해를 찾지 못할 수도 있습니다.
• 시간 효율성: 한 번의 선택으로 문제를 해결하므로 시간이 빠르고 효율적입니다.

 

✅ 알고리즘 동작 원리

1. 문제 분석: 문제를 해결하기 위한 목표와 조건을 파악합니다.
2. 탐색: 매 단계에서 가장 좋은 선택을 합니다.
3. 문제 해결: 모든 단계를 마친 후 최적의 해결책을 도출합니다.

 

 

---

✅ 이해를 돕기 위한 코드

def greedy_coin_change(coins, target):
    coins.sort(reverse=True)  # 큰 동전부터 사용하기 위해 내림차순 정렬
    coin_count = 0
    for coin in coins:
        coin_count += target // coin  # 최대 동전 개수
        target %= coin  # 남은 금액 계산
        if target == 0:
            break
    return coin_count

coins = [1, 5, 10, 25]  # 동전의 종류
target = 63  # 목표 금액
print(f"최소 동전 개수: {greedy_coin_change(coins, target)}")

 

최소 동전 개수: 6

 

동작 원리:

1. 동전 종류 정렬: 동전들을 큰 값부터 작은 값으로 정렬합니다.
2. 동전 선택: 현재 금액을 만들기 위해 가장 큰 동전을 최대한 사용합니다.
3. 남은 금액 계산: 선택된 동전만큼 금액을 차감하고, 남은 금액을 동일한 방식으로 처리합니다.

def activity_selection(activities):
    # 활동들을 종료 시간 기준으로 오름차순 정렬
    activities.sort(key=lambda x: x[1])
    
    # 첫 번째 활동을 선택
    selected_activities = [activities[0]]
    
    # 이후 활동을 확인하며 선택
    last_end_time = activities[0][1]
    for i in range(1, len(activities)):
        # 활동의 시작 시간이 마지막 선택한 활동의 종료 시간보다 크거나 같으면 선택
        if activities[i][0] >= last_end_time:
            selected_activities.append(activities[i])
            last_end_time = activities[i][1]  # 마지막 종료 시간 업데이트
    
    return selected_activities

# 활동: (시작 시간, 종료 시간)
activities = [(1, 3), (2, 5), (4, 7), (6, 8), (5, 9), (8, 10)]
selected = activity_selection(activities)

print("선택된 활동:")
for activity in selected:
    print(f"시작: {activity[0]}, 종료: {activity[1]}")

 

선택된 활동:
시작: 1, 종료: 3
시작: 4, 종료: 7
시작: 8, 종료: 10

 

동작 원리:

1. 먼저 활동들을 종료 시간 기준으로 오름차순 정렬합니다.
   • 예시: [(1, 3), (2, 5), (4, 7), (6, 8), (5, 9), (8, 10)] → 정렬 후 [(1, 3), (2, 5), (4, 7), (5, 9), (6, 8), (8, 10)]
2. 첫 번째 활동 (1, 3)을 선택하고, 이후 활동을 차례로 확인합니다.
   • (2, 5)는 1부터 3까지 진행되므로 선택할 수 없습니다.
   • (4, 7)은 종료 시간인 3 이후에 시작되므로 선택합니다.
   • (5, 9)는 시작 시간이 5이지만, 이전 활동 (4, 7)의 종료 시간 7과 겹치므로 선택하지 않습니다.
   • (6, 8)도 선택할 수 없습니다.
   • (8, 10)은 종료 시간 7 이후에 시작되므로 선택합니다.

따라서, 선택된 활동은 (1, 3), (4, 7), (8, 10) 입니다.