Greedy Algorithm
미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식
장점 : 구현하기 쉽고 빠르다.
단점 : 최적의 답이 보장되지 않는다.
언제 그리디 알고리즘을 사용할까?
- 문제를 해결하는 다른 알고리즘들이 너무 느릴 때
- 완벽한 최적의 답까지 필요하지 않을 때
그리디 알고리즘은 최적의 답을 보장하지 못 하는 단점이 있지만, 그리디 알고리즘이 최적의 답을 보장해주는 문제도 존재한다. 그런 문제를 어떻게 알아볼 수 있을까?
- 최적 부분 구조 (Optimal Substructure) 이 있는 경우
: 부분 문제의 정답을 이용해서 기존 문제의 정답을 구할 수 있는 경우 - 탐욕적 선택 속성 (Greedy Choice Property) 이 있는 경우
: 각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택인 경우
두 경우를 만족하는 문제는 그리디 알고리즘이 최적의 솔루션을 보장한다.
코드잇) 최소 동전으로 거슬러 주기
최소 동전으로 돈을 거슬러 주는 함수를 Greedy Algorithm으로 구현해 보겠습니다.
우리가 작성할 함수 min_coin_count는 거슬러 줘야 하는 총액 value와 동전 리스트 coin_list를 파라미터로 받고, 거슬러 주기 위해 필요한 최소 동전 개수를 리턴합니다.
예를 들어 1170원을 거슬러 주기 위해서는 500원 2개, 100원 1개, 50원 1개, 10원 2개를 줄 수 있기 때문에 6을 리턴하면 되겠죠?
동전의 조합은 항상 500원, 100원, 50원, 10원이라고 가정합시다.
def min_coin_count(value, coin_list):
coin_list = sorted(coin_list, reverse=True)
cnt = 0
for coin in coin_list:
if (value // coin) > 0:
cnt += value//coin
value -= (value//coin)*coin
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))코드잇) 최대 곱 구하기
def max_product(card_lists):
result = 1
for i in card_lists:
result *= max(i)
return result코드잇) 지각 벌금 적게 내기
def min_fee(pages_to_print):
fee_list = sorted(pages_to_print)
people = len(pages_to_print)
total_fee = 0
for fee in fee_list:
total_fee += fee*people
people -= 1
return total_fee코드잇) 수강신청
문제
이번 학기 코드잇 대학교의 수업 리스트가 나왔습니다.
[(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은 파라미터로 전체 수업 리스트를 받고 가능한 많은 수업을 담은 리스트를 리턴합니다.테스트 코드
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)]
def course_selection(course_list):
# 가장 빨리 끝나는 수업
course = [min(course_list, key=lambda x : x[1])]
while True:
# 마지막 수업이 끝나는 시간
end_time = course[-1][1]
# 들을 수 있는 강의리스트
can_courses_list = list(filter(lambda x : x[0] >= end_time, course_list))
# 만약 들을 수 있는 강의 리스트가 없으면 멈춰라
if len(can_courses_list) == 0:
break
# 그중 가장 빨리 끝나는 수업
short_course = min(can_courses_list, key=lambda x : x[1])
# 그 수업을 coure 리스트에 추가해
course.append(short_course)
return course