코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.
미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식
(매 순간마다 탐욕적인 선택을 한다.)
장점: 간단하고 빠르다.
단점: 최적의 답이 보장되지 않는다.
A지점에서 가장 높은곳으로 가고싶으면 어떻게 해야할까? 현재 지점(A)을 기준으로 당장은 C 방향의 경사가 높다. 그리디 알고리즘을 활용하게되면 당장 경사가 높은 C의 방향을 선택한다. 최고로 높은곳은 B이지만 결국은 C에 도달하게 될 것이다.
다음을 만족하는 문제는 Greedy Algirithm이 최적의 답을 보장해준다.
동전의 종류가 500, 100, 50, 10이 있을 때, 최대한 적은 동전으로 돈을 거슬러 주는 문제.
1700원 거슬러 주기 문제
이 4가지 부분문제에 대한 최적의 답을 구하고 4개를 비교하면 기존문제의 답을 구할 수 있다.
동전 거슬러 주기 문제는 최적 부분 구조와 탐욕적 선택 속성을 갖는다. 따라서 이 문제를 그리디 알고리즘으로 풀면 최적의 답이 보장된다.
지금까지 살펴본 개념을 바탕으로 그리디 알고리즘을 활용해 문제를 풀어보자. 모든 문제는 그리디 알고리즘을 통해 최적의 답을 구할 수 있는지 먼저 판별해보고 풀이를 진행하겠다.
최소 동전으로 돈을 거슬러 주는 함수를 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):
# 코드를 작성하세요.
# 테스트
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
def min_coin_count(value, coin_list):
coin_count = 0
for coin in sorted(coin_list, reverse=True):
coin_count += value // coin
value = value % coin
return coin_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
def max_product(card_lists):
# 코드를 작성하세요.# 예시
test_cards = [[1, 2, 3], [4, 6, 1], [8, 2, 4], [3, 2, 5], [5, 2, 3], [3, 2, 1]]
print(max_product(test_cards))
여럿이서 카드 게임을 하고 있는데, 각 플레이어는 3장의 카드를 들고 있습니다. 위의 경우 첫 번째 플레이어는 11, 22, 33을 들고 있고, 두 번째 플레이어는 44, 66, 11을 들고 있고, 세 번째 플레이어는 88, 22, 44를 들고 있는 거죠.
함수 max_product
는 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 리턴합니다.
max_product([[1, 2, 3], [4, 6, 1], [8, 2, 4], [3, 2, 5]])
이 문제를 풀어야 한다.max_product([[1, 2, 3], [4, 6, 1], [8, 2, 4])
를 풀고 3, 2, 5를 각각 곱했을 때 가장 큰 값이 기존 문제의 정답이라고 볼 수 있다.최적 부분 구조와 탐욕적 선택 속성이 존재하기 때문에 그리디 알고리즘으로 최적의 솔루션을 구할 수 있다.
def max_product(card_lists):
# 코드를 작성하세요.
# 테스트
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장의 카드를 들고 있습니다. 위의 경우 첫 번째 플레이어는 11, 22, 33을 들고 있고, 두 번째 플레이어는 44, 66, 11을 들고 있고, 세 번째 플레이어는 88, 22, 44를 들고 있는 거죠.
함수 max_product
는 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 리턴합니다. max_product
를 Greedy Algorithm 방식으로 구현해 보세요.
def max_product(card_lists):
# 코드를 작성하세요.
result = 1
for card_list in card_lists:
result *= max(card_list)
return result
# 테스트
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