[알고리즘 패러다임] 그리디 알고리즘(Greedy Algorithm) - 1

guava·2021년 10월 9일

알고리즘 코드잇

알고리즘의 정석

목록 보기

12/13

코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.

그리디 알고리즘 소개

미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식
(매 순간마다 탐욕적인 선택을 한다.)

장점: 간단하고 빠르다.

단점: 최적의 답이 보장되지 않는다.

A지점에서 가장 높은곳으로 가고싶으면 어떻게 해야할까? 현재 지점(A)을 기준으로 당장은 C 방향의 경사가 높다. 그리디 알고리즘을 활용하게되면 당장 경사가 높은 C의 방향을 선택한다. 최고로 높은곳은 B이지만 결국은 C에 도달하게 될 것이다.

그리디 알고리즘이 유용한 경우

다른 알고리즘들이 느려서 사용하기 힘들 때
애초부터 완벽한 답이 필요 없을 때
그리디 알고리즘이 최적의 답을 보장해 주는 문제일 때. - 효율적이면서도 정확한 솔루션을 얻을 수 있다.

2. 언제 Greedy Algorithm을 사용할까?

다음을 만족하는 문제는 Greedy Algirithm이 최적의 답을 보장해준다.

최적 부분 구조가 있다. (부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것)
탐욕적 선택 속성이 있다. (각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택)

최대한 적은 동전을 사용해서 돈 거슬러 주기 문제

동전의 종류가 500, 100, 50, 10이 있을 때, 최대한 적은 동전으로 돈을 거슬러 주는 문제.

최적 부분 구조가 있는가?

1700원 거슬러 주기 문제

첫 동전으로 500원 1개를 거슬러 준다. → 1200원이 남는다. → 동전을 최대한 적게 사용해서 1200원을 거슬러주는 부분문제가 남는다.
첫 동전으로 100원 1개를 거슬러 준다. → 1600원이 남는다. → 동전을 최대한 적게 사용해서 1600원을 거슬러주는 부분문제가 남는다.
첫 동전으로 50원 1개를 거슬러 준다. → 1650원이 남는다. → 동전을 최대한 적게 사용해서 1650원을 거슬러주는 부분문제가 남는다.
첫 동전으로 10원 1개를 거슬러 준다. → 1690원이 남는다. → 동전을 최대한 적게 사용해서 1690원을 거슬러주는 부분문제가 남는다.

이 4가지 부분문제에 대한 최적의 답을 구하고 4개를 비교하면 기존문제의 답을 구할 수 있다.

탐욕적 선택 속성도 있을까?

이 문제를 그리디 알고리즘을 사용해서 풀면 어떤 탐욕적 선택이 가능할까? 매 순간마다 가장 큰 돈을 거슬러 준다.
매 순간마다 가능한 큰 동전을 선택하는게 가장 좋은 선택이라는걸 증명할 수 있는가? (O) 증명: 500 = 1005, 100=502, 50=10*5이다. 가능한 큰 동전을 주는게 더 좋다고 확신할 수 있다.

동전 거슬러 주기 문제는 최적 부분 구조와 탐욕적 선택 속성을 갖는다. 따라서 이 문제를 그리디 알고리즘으로 풀면 최적의 답이 보장된다.

3. 그리디 알고리즘 개념

Greedy Algorithm을 사용하기위한 필수 조건은 없다.
Greedy Algorithm을 사용해서 최적의 솔루션을 구하기 위한 필수 조건이 있다. 바로 그 문제에 최적 부분 구조와 탐욕적 선택 속성이 존재할 때이다.

지금까지 살펴본 개념을 바탕으로 그리디 알고리즘을 활용해 문제를 풀어보자. 모든 문제는 그리디 알고리즘을 통해 최적의 답을 구할 수 있는지 먼저 판별해보고 풀이를 진행하겠다.

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

해설

누적 동전 개수를 저장하기 위한 coin_count 변수를 정의했다.
탐욕적인 선택을 하기 위해 coin_list를 내림차순으로 정렬했다.

코드

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

5. 최대 곱 구하기 분석

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는 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 리턴합니다.

최적 부분 구조가 있는가? (O)

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를 각각 곱했을 때 가장 큰 값이 기존 문제의 정답이라고 볼 수 있다.
부분 문제의 정답을 이용해서 기존 문제의 정답을 풀었다. 최적 부분 구조가 존재한다.

탐욕적 선택 속성이 존재하는가? (O)

탐욕적 선택은 각 카드뭉치에서 가장 큰 값을 고르는 것이다.
이 문제에서는 각 값이 모두 양수이기 때문에 탐욕적선택=최적의 선택으로 볼 수 있다.
탐욕적 선택 속성이 존재한다.

최적 부분 구조와 탐욕적 선택 속성이 존재하기 때문에 그리디 알고리즘으로 최적의 솔루션을 구할 수 있다.

6. 최대 곱 구하기

문제

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

함수 max_product는 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 리턴합니다. max_product를 Greedy Algorithm 방식으로 구현해 보세요.

풀이

Brute Force방식으로 풀면 모든 곱을 구한 후 비교한다. 이는 굉장히 비효율적이다.
각 카드뭉치에서 가장 큰 값을 선택해서 곱한다.

코드

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

guava

이전 포스트

[알고리즘 패러다임] 다이나믹 프로그래밍 (Dynamic Programming) - 2

다음 포스트