[5주차] 그리디 알고리즘

그리디 알고리즘?

매 순간 최선이라고 생각되는 선택을 하여 전체 문제의 최적해를 구하는 알고리즘 전략

탐욕법이라고 부르기도 한다.

 

특징

• 탐욕적 선택 속성 : 매 순간 가장 최적의 선택을 하는 것이 최종 해답의 최적성을 보장하는 속성
• 최적 부분 구조 : 전체 문제의 최적해가 부분 문제의 최적해들로 구성될 수 있는 구조

 

장점

1. 빠른 시간 복잡도 : 보통 정렬 O(n log n) + 선형 스캔 O(n) 등으로 매우 효율적이다.
2. 메모리 적음 : 상태 저장(테이블) 필요성이 적다.(대부분 상수 또는 선형)
3. 구현 쉬움 : 코드가 짧고 디버깅이 쉽다.

 

단점

 

1. 항상 최적이 아니다 : 잘못된 그리디 규칙은 전혀 최적해를 주지 못한다.
2. 증명 필요 : 그리디 방법이 최적임을 보이려면 교환 주장(exchange argument) 등으로 증명해야 한다.
3. 문제 인식 필요 : 문제의 구조를 잘 파악하지 못하면 그리디를 적용하면 틀린 경우도 있다.

 

문제 유형

● 활동 선택 문제

활동 번호	시작 시간	종료 시간
A1	1	2
A2	3	4
A3	0	6
A4	5	7
A5	8	9

activities = [(1,2), (3,4), (0,6), (5,7), (8,9)]
activities.sort(key=lambda x: x[1])  # end time 순 정렬

result = []
current_end = 0

for start, end in activities:
    if start >= current_end:
        result.append((start, end))
        current_end = end

print(result)  # [(1,2), (3,4), (5,7), (8,9)]

 

 

● 거스름돈 계산

 

 

목표: 최소 개수의 동전으로 특정 금액을 만들기

전략: 큰 동전부터 최대한 사용

 

단계	사용 동전	남은 금액	동전 개수
500원 사용	1260 → 1260 // 500 = 2개	1260 - 1000 = 260	2개
100원 사용	260 → 260 // 100 = 2개	260 - 200 = 60	4개
50원 사용	60 → 60 // 50 = 1개	60 - 50 = 10	5개
10원 사용	10 → 10 // 10 = 1개	10 - 10 = 0	✅ 6개

coins = [500, 100, 50, 10]
target = 1260

count = 0
for coin in coins:
    count += target // coin  # 해당 동전을 최대 몇 개 쓸 수 있는가
    target %= coin           # 남은 잔돈 갱신

print(count)  # 출력: 6