알고리즘: 그리디 알고리즘(Greedy Algorithm) 공부하고 예제 한번 풀어보자!

그리디 알고리즘이란(Greedy Algorithm)이란?

 

 

 

뜻 그대로 탐욕스런 알고리즘이라고 생각하면 쉽다. 미래를 내다 보지 않고

 

당장 눈 앞에 보이는 최적의 선택을 하는 방식이다. 

 

그리디 알고리즘은 간단하고 빠르지만, 항상 최적의 답이 보장되지는 않는다.

 

그래서 보통 최적의 답이 필요 없는 경우에 사용하지만 

 

그리디 알고리즘이 최적의 답을 보장해 주는 문제도 있다.

 

 

 

그리디 알고리즘은 다음과 같은 조건을 만족할때 최적의 답을 보장한다.

(다음과 같은 조건이 없어도 그리디 알고리즘을 사용할 수는 있다.)

 

 

→ 최적 부분 구조가 있을 때

   

 문제를 부분 문제로 나누어 해결하여 기존 문제의 답을 찾아낼 수 있는 경우    

 

 

→ 탐욕적 선택 속성을 갖고 있을 때 

 

  다이나믹 프로그래밍처럼 답의 모든 부분을 고려하지 않고

탐욕적 선택만 하더라도 최적인 답을 찾을 수 있는 경우

 

 

 

 

1. 최소 동전으로 거슬러 주기

 

 

coin_list에 있는 최소한의 동전 value값 거슬러 주기 

 

def min_coin_count(value, coin_list):
    
    coin_list.sort(reverse = True)  # 역순으로 먼저 정렬
    
    count = 0
    
    for coin in coin_list:
        
        count += (value // coin)    # 큰 동전 순으로 나누어준다
        value %= coin
    
    return count
    
    
    
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))

 

10
5
49
70

 

선택한 탐욕적 속성 = 큰 동전을 먼저 거슬러 주면 최소 동전으로 거슬러 줄 수 있을 것이다.

 

 

※ 만약 동전 리스트 값이 [100 , 70, 10]이였다면 위 조건은 만족하지 않는다. 

 

140원을 거슬러 준다고 했을 때

100 + 10 x 4 의 경우 사용한 동전 갯수는 5개

70 x 2 의 경우 사용한 동전 갯수 2개 이므로 

 

큰동전을 먼저 거슬러 주는 탐욕적 선택은 옳지 않다. 

 

 

 

2. 최대 곱 구하기 

 

 

여럿이서 카드 게임을 하고 있는데, 각 플레이어는 3장의 카드를 들고 있다.

 

첫번째 플레이어의 경우는 1, 6, 5의 카드를 들고 있고, 두번째 플레이어의 경우 4, 2, 3의 카드를 들고 있다.

 

플레이어들끼리 카드를 한장씩 냈을 때, 낸 카드의 곱의 최대값을 구하라

 

def max_product(card_lists):
    
    product = 1  # 최대 곱
    
    for card in card_lists:
        
        product *= max(card)
        
        
        
    return product



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))

 

24
244944
10800
12600

 

선택한 탐욕적 속성 = 낸 카드들 중에서 가장 큰 값을 고르면 최대값을 만들 수 있을 것이다. 

 

 

 

3. 지각 벌금 적게 내기

 

 

익중이네 밴드부는 매주 수요일 오후 6시에 합주를 하는데요. 멤버들이 너무 상습적으로 늦어서, 1분에 1달러씩 내야 하는 벌금 제도를 도입했습니다.

 

그런데 마침 익중이와 친구 넷이 놀다가 또 지각할 위기입니다. 아직 악보도 출력해 놓지 않은 상황이죠.

 

어차피 같이 놀다 늦은 것이니 벌금을 다섯 명이서 똑같이 나눠 내기로 하고, 벌금을 가능한 적게 내는 방법을 고민해 보기로 합니다.

 

다섯 사람이 각각 출력해야 하는 페이지 수는 3장, 1장, 4장, 3장, 2장입니다. 프린터는 한 대밖에 없고, 1장을 출력하기 위해서는 1분이 걸립니다.

 

현재 순서대로 출력한다면,

1. 첫 번째 사람: 3분 지각
2. 두 번째 사람: 3 + 1분 지각
3. 세 번째 사람: 3 + 1 + 4분 지각
4. 네 번째 사람: 3 + 1 + 4 + 3분 지각
5. 다섯 번째 사람: 3 + 1 + 4 + 3 + 2분 지각

총 39달러의 벌금을 내야 합니다.

 

흠… 더 적게 내는 방법이 있지 않을까요?

 

def min_fee(pages_to_print):
    
    min_fee = 0  # 최소 벌금
    
    pages_to_print.sort()
    
    for i in range(0, len(pages_to_print)):
        min_fee += ((len(pages_to_print) - i) * pages_to_print[i])
        
    return min_fee



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]))

 

39
10
32
188

 

선택한 탐욕적 속성 = 지각 비용이 적은 순서로 지각 벌금을 낸다면 가장 적은 지각 비용을 낼 것이다!

 

 

 

4. 수강 신청

 

 

이번 학기 코드잇 대학교의 수업 리스트가 나왔습니다.

 

[(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 6), (13, 16), (9, 11), (1, 8)]

 

리스트에 담겨있는 튜플들은 각각 하나의 수업을 나타냅니다. 각 튜플의 0번째 항목은 해당 수업의 시작 교시, 그리고 1 번 항목은 해당 수업이 끝나는 교시입니다.

 

예를 들어서 0번 인덱스에 있는 튜플값은 (4, 7)이니까, 해당 수업은 4교시에 시작해서 7교시에 끝나는 거죠.

 

(2, 5)를 듣는다고 가정합시다. (4, 7) 수업은 (2, 5)가 끝나기 전에 시작하기 때문에, 두 수업은 같이 들을 수 없습니다. 반면, 수업 (1, 3)과 (4, 7)은 시간이 겹치지 않기 때문에 동시에 들을 수 있습니다.

 

(단, (2, 5), (5, 7)과 같이 5교시에 끝나는 수업과 5교시에 시작하는 수업은 서로 같이 듣지 못한다고 가정합니다)

 

열정이 불타오르는 신입생 지웅이는 최대한 많은 수업을 들을 수 있는 수업 조합을 찾아주는 함수 course_selection 함수를 작성하려고 합니다.

 

course_selection은 파라미터로 전체 수업 리스트를 받고 가능한 많은 수업을 담은 리스트를 리턴합니다.

 

def course_selection(course_list):
    
    # course_list[?][1] 값을 기준으로 정렬해 줍시당 
    
    mini = course_list[0][1]
    
    for i in range(0, len(course_list) - 1):
        for j in range(i, len(course_list)):
            if course_list[i][1] > course_list[j][1]:
                course_list[i], course_list[j] = course_list[j],course_list[i]


    # 선택한 강의들을 넣어줄 리스트
    selected_course = [course_list[0]]
    
    i = 1
    prev = selected_course[0][1]
    
    while i < len(course_list):
        
        if prev < course_list[i][0]:
        
            selected_course.append(course_list[i])
            
            prev = course_list[i][1]  # selected_course에 방금 넣어준 값과 비교를 위해 
           
        i += 1
        
        
    return selected_course
             
    
    

print(course_selection([(6, 10), (2, 3), (4, 5), (1, 7), (6, 8), (9, 10)]))
print(course_selection([(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]))
print(course_selection([(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 5), (13, 16), (9, 11), (1, 8)]))

 

[(2, 3), (4, 5), (6, 8), (9, 10)]
[(1, 2), (3, 4), (5, 7), (8, 9)]
[(1, 3), (4, 7), (8, 10), (13, 16)]

 

선택한 탐욕적 속성 = 가장 빨리 끝나는 수업 순으로 나열하면 최대로 수강 신청할 수 있을 것이다!

 

 

 

 

 

 

문제출처: 코드잇(codeit)