Greedy Algorithm 2

저번 시간에는 Greedy Algorithm의 개념과 필요 조건, 사례를 함께 살펴봤습니다.

이번 시간에는 더 다양한 Greedy Algorithm의 사례를 접하고 이 알고리즘에 대한 이해를 더 높여보는 시간을 가져봅시다.

🐖 최대 곱 구하기

여러 명이 모여 카드 게임을 하고 있습니다. 각 선수는 3장의 카드를 들고 있는데요. 예를 들어, 한 선수는 2, 3, 4를 들고 있고 다른 선수는 3, 8, 6을 들고 있으며 마지막 선수는 4, 5, 7을 들고 있습니다.

함수 max_card_product는 한 사람당 카드를 하나씩 뽑아서 그 수들을 모두 곱했을 때 가능한 최대의 곱을 리턴합니다.

❗ 분석

문제를 풀기 전 Greedy Algorithm으로 최적의 답을 구할 수 있는지부터 분석해봅시다. 문제가 두 가지 조건을 충족하는지 확인해야 되죠?

먼저, 최적 부분 구조가 있는지를 봅시다. 예시로 한 문제를 보죠.

max_card_product[[2, 3, 5], [7, 3, 5], [4, 5, 2], [8, 5, 4]]

이 문제는 어떤 부분 문제로 나눌 수 있을까요? 이 문제를 풀기 위해서는 우선 max_card_product([[2, 3, 5], [7, 3, 5], [4, 5, 2]])을 풀어야 합니다. 그리고 이 결과값을 8과 곱한 값, 5와 곱한 값, 4와 곱한 값 중 가장 큰 값이 기존 문제의 정답이 됩니다.

부분 문제의 정답을 이용해서 기존 문제의 정답을 구할 수 있기 때문에, 이 문제에는 최적 부분 구조가 있다고 할 수 있습니다.

다음으로 탐욕적 선택 속성을 가지고 있는지도 확인해봅시다. 이 문제를 풀기 위해서 어떤 탐욕적인 선택을 할 수 있을까요? 가장 쉽게 생각할 수 있는 답은 각 카드 리스트에서 가장 큰 값을 고르는 것입니다.

그런데 과연 이런 선택이 최적의 답을 보장해 줄 수 있을까요? 카드의 숫자들은 모두 0보다 큰 양수입니다. 따라서, 무조건 큰 숫자를 고르는 게 최적의 선택이라고 확신할 수 있죠. 그렇기 때문에 이 문제는 탐욕적 속성도 가지고 있다고 할 수 있습니다.

결과적으로 최적 부분 구조와 탐욕적 선택 속성 둘 모두를 가지고 있기 때문에 이 문제는 Greedy Algorithm을 이용해서 최적의 답을 구할 수 있습니다.

❗ 코드 구현

이제 코드로 구현해봅시다.

이 문제에서 핵심은 각 단계에서 시도할 수 있는 탐욕적인 선택을 찾는 것입니다.

앞서 동전 문제에서 가장 큰 액수의 동전을 먼저 사용하는 것과 마찬가지로 이 문제에서는 카드 리스트 중 가장 큰 수를 뽑아 사용하는 것이 탐욕스러운 선택이 됩니다.

먼저, 누적된 곱을 저장할 수 있는 공간인 product 변수를 선언합니다.

proudct = 1

만약 여기서 초기값을 0으로 두면 어떻게 될까요? 0은 다른 어떤 수와 곱해도 0이 되므로 초기값으로는 적절하지 않습니다.

이제 반복문을 돌면서 카드 리스트를 하나씩 봐야 합니다. 그리고 product에 각 카드 리스트의 최댓값을 곱해주기만 하면 됩니다.

주의해야 할 것은 각 리스트에서 최댓값 두개를 골라 곱을 구하는 것이 아니라 각 리스트의 모든 최댓값끼리 곱해 최대의 곱을 구한다는 점입니다.

for card_list in card_lists:
    product += max(card_list)

꽤 간단하죠?

이제 전체 코드와 예시를 봅시다.

def max_card_product(card_lists):
    
    product = 1

    for card_list in card_lists:
        product *= max(card_list)

    return product

test_cards1 = [[2, 7, 6], [5, 3, 4]]
print(max_card_product(test_cards1))

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

35
258048

🐖 지각 벌금 적게 내기

타키탸키네 반 학생들은 평일 오전 9시까지 등교를 해야합니다. 그런데 학생들이 너무 상습적으로 늦는 바람에 1분에 1달러씩 내야 하는 벌금 제도를 도입했습니다.

그런데 타키탸키는 전날 친구들과 밤새 게임을 하다가 또 지각할 위기를 맞았습니다. 더욱 문제인 것은 음악 시간에 제출할 악보를 아직 출력하지 못해서 등교 전에 출력을 하러 가야한다는 것입니다.

친구들이 모두 함께 지각을 하게 생겼으니 벌금을 일곱 명이서 똑같이 나눠 내기로 하고 가능한 적게 벌금을 내는 방법을 고민해보기로 했습니다.

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

만약 순서대로 출력한다면,

A: 4분 지각
B: 4 + 2분 지각
C: 4 + 2 + 5분 지각
.
.
.
G: 4 + 2 + 5 + 4 + 3 + 2 + 1분 지각

총 95달러의 벌금을 내야합니다. 꽤 비싸네요. 더 적게 낼 수 있는 방법은 없을까요?

출력할 페이지 수가 담긴 리스트 pages_to_print를 파라미터로 받고 최소 벌금을 리턴해주는 함수 min_fine을 작성해 봅시다.

❗ 분석

문제를 풀기 전, Greedy Algorithm으로 푸는 것이 효율적일지를 따져봅시다.

위 문제는 최적 부분 구조를 가지고 있나요?

A가 먼저 출력한다고 가정하면,

A: 4분 지각
B: 4 + a분 지각
C: 4 + a + b분 지각
.
.
.
G: 4 + a + b + c + d + e + f분 지각

이렇게 됩니다. A를 기다리느라 모든 친구들이 각각 최소 4분씩을 지각하게 되죠. 그 후에는 남은 친구들이 어떤 순서로 출력하는 게 좋을지 결정해야 하는데요.

코드로 구현하면 대략 이렇습니다.

4 * 7 + min_fine([2, 5, 4, 3, 2, 1])

만약 G가 먼저 출력한다고 가정하면 이렇게 되죠.

1 * 7 + min_fine([4, 2, 5, 4, 3, 2])

이런 식으로 첫 사람을 기준으로 값을 다르게 정할 수 있습니다. 이는 위 문제의 부분 문제가 되는데요. 이 부분 문제를 풀고 서로 비교해서 최적의 경우를 선택하면 되겠습니다. 따라서, 위 문제는 최적 부분 구조를 가지고 있다고 할 수 있습니다.

그렇다면 위 문제에서 매 단계마다 가장 좋아보이는 선택은 무엇일까요? 위 사례에서 잠깐 봤듯이 일곱 명이 모두 4분을 기다리는 것보다 1분만 기다리는 것이 더 이득일 것 같습니다.

따라서, 기다리는 시간을 최소화하기 위해서는 페이지 수가 적은 사람 순으로 출력하는 것이 최선인 것 같네요. 이로 미루어 봤을 때, 위 문제는 탐욕적 선택 속성도 가지고 있다고 할 수 있습니다.

두 조건을 모두 충족하기 때문에 위 문제는 Greedy Algorithm으로 최적의 답을 구할 수 있습니다.

❗ 코드 구현

이제 코드로 구현해봅시다.

카드 곱 문제와 같이 가장 탐욕스러운 선택부터 찾아보도록 하죠. 이 문제의 경우에는 기다리는 시간을 최소화하기 위해 페이지 수가 적은 사람 순으로 출력하면 된다고 했었죠? 그럼 리스트를 오름차순으로 정렬해야겠네요.

sorted_list = sorted(pages_to_print)

다음으로 총 벌금을 담을 변수가 필요합니다.

total_fine = 0

마지막으로 반복문을 돌며 총 벌금을 계산하면 됩니다.

for i in range(len(sorted_list)):
    total_fine += sorted_list[i] * (len(sorted_list) - i)

이제 전체 코드와 예시를 봅시다.

def min_fine(pages_to_print):

    sorted_list = sorted(pages_to_print)

    total_fine = 0

    for i in range(len(sorted_list)):
        total_fine += sorted_list[i] * (len(sorted_list) - i)

    return total_fine

print(min_fine([4, 2, 5, 4, 3, 2, 1]))

66

---

지금까지 Greedy Algorithm의 다양한 사례를 접해봤습니다. 이제 Greedy Algorithm이 이해 가시나요?

사례를 몇 번 접하고 나니 패턴이 보이기 시작하네요. 탐욕적인 선택 속성에 따라 주어진 리스트를 오름차순이나 내림차순으로 정렬하고 누적 값을 변수에 저장해서 반환하는 패턴이 말이죠.

이것으로 알고리즘 챕터를 모두 끝냈습니다. 이제까지 배운 여러 가지 알고리즘 개념들을 활용하여 더 다양한 문제들을 풀어봅시다. 수고 많으셨습니다😊😊😊

* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.