[알고리즘] Greedy(탐욕법)

 

 

 

그리디 알고리즘(탐욕법, Greedy Algorithm)이란?

 

 

이미지출처: https://velog.io/@ming/Greedy-Algorithm

 

그리디 알고리즘이란 최적화 문제를 해결하기 위한 알고리즘입니다.

Greedy는 영어로 탐욕이라는 의미를 가지고 있습니다.

당장의 눈앞의 이익만 추구하는 '탐욕적인' 행동을 하면서

현재 상황에서 가장 좋은 선택을 진행합니다.

 

 

---

1. 기본 원리

 

1-1. 탐욕적 선택 속성(Greedy Choice Property)

 

각 단계에서 지역적으로 최적의 선택이 전체 문제의 최적의 해로 이어진다는 속성입니다.

=> 현재 상태에서의 최적의 선택을 정의

 

1-2. 최적 부분 구조(Optimal Substructure)

 

전체 문제의 최적해가 부분 문제의 최적의 해를 포함하는 구조를 말합니다.

=> 전체 문제와 부분 문제 간의 관계를 정의

 

 

---

2. 문제 해결 절차

 

1. 선택 절차(Selection Procedure) : 현재 상태에서 가장 최적의 해를 선택합니다.

2. 적절성 검사(Feasibility Check): 선택한 해가 문제의 조건을 만족하는지 확인합니다.

3. 선택한 해를 Solution Set에 추가합니다.

4. 해답 검사(Solution Check): 새로운 Solution Set이 전체 문제를 해결했는지 확인합니다.

해결하지 못했다면 선택 절차로 돌아가 반복. 해결 되었다면, 종료합니다.

 

---

 

3. 예제 문제 (Python)

 

문제1. 활동 선택 문제(Activity Selection Problem)

#문제 설명 

여러 activity가 있고, 각 activity의 시작시간과 종료 시간이 있을 때,
한 사람이 최대한 많은 activity에 참여할 수 있는 activity을 선택합니다.

# activity 시작시간과 종료시간: 

activity1 : 1시~4시
activity2 : 3시~5시
activity3 : 0시~6시
activity4 : 5시~7시

------
# 문제 해결 절차
1. 선택절차: 가장 일찍 끝나는 activity 선택.
2. 적절성 검사: 현재 activity의 시작 시간이 마지막으로 선택된 activity 종료시간 이후인지 확인.
3. 해답 검사: 모든 activity를 한 번씩 검토

 

def activity_selection(acvivities):
	# activities는 tuple를 요소로 갖는 리스트형식으로 제공됨 [(1,4), (3,5)...]
    
    # 1. 선택절차: 가장 일찍 끝나는 activity 선택
    activities.sort(key=lambda x: x[1])
    
    # 2. 적절성 검사: 현재 activity의 시작 시간이 마지막으로 선택된 activity 종료시간 이후인지 확인.
    # 3. 해답 검사: 모든 activity를 한 번씩 검토
    selected = [activities[0]]
    last_finish_time = activities[0][1]
    for i in range(1, len(activities)):
    	start_time, finish_time = activities[i]
        
        if start_time >= last_finish_time:
        	selected.append(activities[i])
            last_finish_time = finish_time
    
    return selected
    
activities = [(1, 4), (3, 5), (0, 6), (5, 7)]
selected_activities = activity_selection(activities)

print("선택된 활동:", selected_activities) #선택된 활동: [(1, 4), (5, 7)]
print("선택된 활동 수:", len(selected_activities)) #선택된 활동 수: 2

 

 

 

문제2. 동전 거스름돈 문제(Coin Change Problem)

#문제 설명 

주어진 금액을 거슬러 주기 위해 필요한 최소한의 동전 개수를 구하는 문제입니다.

# 동전 종류
500원, 100원 50월 10월 1원

#거스름돈 금액 
1260원

------
# 문제 해결 절차
1. 선택절차: 가장 큰 단위의 동전부터 선택.
2. 적절성 검사: 현재 동전을 사용할 수 있는지 확인.(거스름돈 이하인지)
3. 해답 검사: 거스름돈이 0원이 되었는지 확인.

def coin_change(coins, amount):
	#1. 선택절차: 가장 큰 단위의 동전부터 선택.
    coins.sort(reverse=True)
    
	#2. 적절성 검사: 현재 동전을 사용할 수 있는지 확인.(거스름돈 이하인지)
    count = 0
    coin_used = {}
    
   	for coin in coins:
    	# 현재 선택된 동전으로 거스름돈이 가능한 최대 개수 계산
    	num_coins = amount // coin 
        if num_coins > 0:
        	coin_used[coin] = num_coins
            count += num_coins
            amount -= coin * num_coins
		# 3. 해답 검사: 거스름돈이 0원이 되었는지 확인.
        	if amount == 0:
            	break
            
	if amount > 0:
    	return "거스름돈 거슬러 줄 수 없음"
 	
    return count, coin_used
    

coins = [500, 100, 50, 10, 1]
amount = 1260
count, coin_used = coin_change(coins, amount)
print(f"필요한 동전 개수: {count}") #필요한 동전 개수: 6
print(f"동전 사용 내역: {coin_used}") #동전 사용 내역: {500: 2, 100: 2, 50: 1, 10: 1}