[자료구조] 9. Greedy Algorithm 이해하기(feat. codestates, self tutorial)

 

 

 

 

 

안녕하십니까 다제입니다. 

 

오늘은  Greedy Algorithm에 대해서 알아보도록 하겠습니다. 

 

언제나 알고리즘은 장단점이 있으며, 그 상황에 맞게 적절히 사용하는게 중요하고 누차 말씀드리고 있습니다. 

 

오늘도  Greedy Algorithm가 무엇이며, 장단점과 언제 사용해야하는지, 소스코드까지 같이 살펴보도록 하겠습니다. 

 

 

---

1. 정의

매순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 최적해에 도달하는 기법

 

2. 개요 

우리는 앞에서 DP(dynamic programming)에 대해서 배웠습니다. DP는 모든 경우의 수를 따져본다는 단점이 있습니다. 

이러한 단점을 극복하기 위해서 Greedy Algorithm입니다. 위에서 언급한 바와 같이 Greedy Algorithm는 항상 최적해를 보장하진 않지만 모든 경우의 수를 따지지 않고 Local optimal을 빠르게 계산할 수 있습니다.

 

3. 장단점

장점 : 간단하고 빠르다. 

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

 

4. 언제 사용할까요?

 -. 다른 알고리즘이 너무 느려서 사용할 수 없을 때 

 -. 최적의 답이 필요 없을 때 

 -. 최적 부분 구조(optimal substructure), 탐욕적 선택 속성(Greedy Choice Property)을 만족할 때 

예를 하나 들어보겠습니다. 

 

우리가 2000원을 거슬러줘야 하는 상황에 대해서 생각을 해볼까요?

500원, 100원, 50원, 10원 중에서 선택하여 2000원을 거슬러 주면 됩니다. 

 

돈을 거슬러주는 방법은 여러가지가 있습니다.

500원 동전 4개로 구성해서 돈을 거슬러주어도 되고, 500원 2개 + 100원 10개로 거슬러 주어도 됩니다.

 

이렇게 작은 단위로 나누어서 문제를 풀 수 있는 구조를 최적 부분 구조라고 합니다. 

 

또한, 탐욕적 선택 속성을 적용하여 돈을 거슬러준다는 것은 가장 큰 금액의 동전으로 동전 수가 최소가 되게 거슬러주는 것을 말합니다. 즉, 500원짜리로 4개로 돈을 거슬러주는 것이 탐욕적 선택 속성을 적용한 것이죠!

 

5. 소스코드

돈을 거슬러주는 프로그램을 구현해보았습니다. 

 

def coin_divide_count(money, set_coin_list):

    set_coin_list = sorted(set_coin_list, reverse=True)
    count = 0 
    first = money//set_coin_list[0]
    count = count + first
    for i in range(len(set_coin_list[1:])):
        second = (money%set_coin_list[i])//set_coin_list[i+1]
        count = count + second
        
    return count
    
    
# 테스트
default_coin_list = [100, 500, 10, 50]
print(coin_divide_count(11100, default_coin_list)) # 정답 : 23
print(coin_divide_count(12650, default_coin_list)) # 정답 : 27

 

위 코드를 아래와 같이 간결하게 줄일 수 있습니다. 

def coin_divide_count(money, set_coin_list):
    for coin in sorted(set_coin_list, reverse=True):
        # 현재 동전으로 몇 개 거슬러 줄 수 있는지 확인합니다.
        count += (money // coin)

        # 잔액을 계산합니다.
        # %=는 나눈 나머지 값을 다시 money에 반영해주는 코드 입니다. 
        money %= coin
 
        
    return count

 

 

코드가 이해가 되지 않으시면 반드시 vscode를 통해서 디버그를 찍어보시는 것을 추천드립니다. 

 

오늘도 Greedy Algorithm에 대해서 알아보았습니다. 

 

이해가 안되시는 부분이 있다면 언제든 댓글부탁드립니다. 

 

감사합니다.