그리디알고리즘(Greedy Algorithm)

그리디 알고리즘이란?!

미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식 

A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment. 
It doesn't worry whether the current best result will bring the overall optimal result.

 

장점 & 단점

장점: 간단하고 빠르다  
단점: 최적의 답이 보장되지 않는다

When to use?!

다른 알고리즘 방법들이 너무 느릴 때  
최적의 답이 필요 없을 때  

feat.최적의 답을 구해주는 경우도 있다?!

1. 탐욕적 선택 속성(Greedy Choice Property)  
2. 최적 부분 구조(Optimal Substructure)

 

실습1  

# 최소 동전으로 거슬러주기
=> 가장 큰 동전액수로 먼저 거슬러주는것이 최선의 선택!

def min_coin_count(value, coin_list):     
    coin_list.sort(reverse=True)

    idx = 0 
    cnt = 0
    while idx != len(coin_list):
        changed =  value % coin_list[idx] 
        cnt += value // coin_list[idx]
        
        if changed < coin_list[idx]:
            idx += 1             
            value = changed
        elif changed == 0:
            return 
    
    return cnt 

# 테스트
default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
print(min_coin_count(1700, default_coin_list))
print(min_coin_count(23520, default_coin_list))
print(min_coin_count(32590, default_coin_list))


# 다른풀이 2
def min_coin_count(value, coin_list): 
    cnt = 0 
    for coin in sorted(coin_list, reverse=True):
        cnt += (value//coint)  # 몇개 거슬러 줄 수 있는지 확인하깅
        value %= coin  # 잔액을 계산
    return cnt

 

실습2  

# 최대곱구하기 =>  card_lists중에서 가장 큰 수를 뽑는 것이 최선의 선택!
def max_product(card_lists):
    answer = 1
    new_card_list =  [sorted([element for element in card], reverse=True) for card in card_lists]
    for card in new_card_list:
        max_number = card[0]
        answer *= max_number
    return answer  

# 테스트
test_cards1 = [[1, 6, 5], [4, 2, 3]]
print(max_product(test_cards1))

test_cards2 = [[9, 7, 8], [9, 2, 3], [9, 8, 1], [2, 8, 3], [1, 3, 6], [7, 7, 4]]
print(max_product(test_cards2))

test_cards3 = [[1, 2, 3], [4, 6, 1], [8, 2, 4], [3, 2, 5], [5, 2, 3], [3, 2, 1]]
print(max_product(test_cards3))

test_cards4 = [[5, 5, 5], [4, 3, 5], [1, 1, 1], [9, 8, 3], [2, 8, 4], [5, 7, 4]]
print(max_product(test_cards4))


# 다른풀이2 
def max_product(card_lists):
    # 코드를 작성하세요.
    answer = 1
    for card in card_lists:
        answer *= max(card)
    return answer

 

실습3

 

# 지각 벌금 적게 내기 - 우선 오름차순으로 정렬을 한 다음에, 작은 수를 가장 많이 더해주는 방식!
def min_fee(pages_to_print):
    # 코드를 작성하세요. 
    answer = 0 
    pages_to_print.sort()     # 0, 0 +1, 0,1,2, 0,1,2,3
    for i in range(len(pages_to_print)):
        for j in range(i+1):
            answer += pages_to_print[j]
    return answer     

# 테스트
print(min_fee([6, 11, 4, 1]))
print(min_fee([3, 2, 1]))
print(min_fee([3, 1, 4, 3, 2]))
print(min_fee([8, 4, 2, 3, 9, 23, 6, 8]))



# 다른풀이2
def min_fee(pages_to_print):
    # 인풋으로 받은 리스트를 정렬시켜 준다
    sorted_list = sorted(pages_to_print)

    # 총 벌금을 담을 변수
    total_fee = 0

    # 정렬된 리스트에서 총 벌금 계산
    for i in range(len(sorted_list)):
        total_fee += sorted_list[i] * (len(sorted_list) - i)

    return total_fee

출처: 코드잇