[Python] 그리디 알고리즘의 모든 것 | 그리디 알고리즘 개념 설명 및 예제 코드

** '코딩테스트 합격자 되기 파이썬편' 서적을 바탕으로 작성한 글입니다. **

 

 

1. 그리디 알고리즘의 개념

 

'그리디(greedy)'란 '탐욕스러운/욕심이 많은' 이라는 의미이다.

그리디 알고리즘은 문제 해결 과정에서 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택은 번복하지 않는다.

이에 따라 그리디 알고리즘은 "지역 최적해"를 추구한다고 말하기도 한다. 즉, 부분벅으로는 최적해를 구한다고 할 수 있어도 전체적으로 최선의 해라고는 말할 수 없다는 특징을 갖고 있다. 

 

<예시>

손님에서 8원을 거슬러 줘야 하는데 계산원이 보유한 동전의 종류가 5, 4, 1뿐이라고 가정해보자.

이때 '동전의 개수를 가장 적게' 만들기 위한 task에서 그리디 알고리즘을 활용해보자.

 

그리디 알고리즘은 "현재 상황에서 가장 최선의 선택"을 하므로 현재 상황에서 취할 수 있는 최선의 전략은 가장 값이 큰 동전부터 주는 것이기에 '5원'부터 생각하게 된다.

5원을 먼저 확보하면 8-5=3원이 남게 되는데, 이 상황에서 취할 수 있는 최선의 전략은 오직 1원 3개를 사용하는 방법 뿐이다. 따라서 이 그리디 알고리즘으로는 4개의 동전을 사용하게 된다.

그러나 사람의 직관으로 생각해보면 알 수 있듯 이는 최선의 방법이 아니며 4원짜리 동전 2개만으로도 문제를 해결할 수 있다. 

이것이 즉 그리디 알고리즘이 지역 최적해를 추구하지만 전체 최적해를 보장하지 않는다는 것을 입증한다.

 

하지만 그리디 알고리즘은 특정한 상황에서 최적해를 보장하므로 이를 잘만 활용하면 문제를 잘 해결할 수 있다.

여기서 말하는 '특정한 상황'이란 다음 2가지를 의미한다.

• 최적 부분 구조 (optimal substructure) : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치
• 그리디 선택 속성 (greedy selection property) : 선택 과정이 다른 과정에 영향을 주지 않음

그리디 알고리즘이 항상 최적해를 도출하지는 못한다는 한계점이 있지만, 빠른 시간 내에 근사해를 제공하는 효율적인 방법 중 하나이므로 문제의 특성과 알고리즘 선택 기준을 잘 이해하면 매우 유용하게 활용할 수 있다.

 

이제 그리디 알고리즘을 쓰면 좋은 상황을 하나씩 알아보도록 하자.

 

 

 

2. 최소 신장 트리 (minimum spanning tree : MST)

 

Q. 신장 트리란?

- 모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프

 

 

Q. 최소 신장 트리(MST)란?

- 신장 트리 중 간선의 가중치 합이 최소인 것

 

위 예제 사진에서 볼 수 있다시피 MST는 하나가 아닌 여러 개일 수도 있다.

MST는 실생활에서도 굉장히 많이 사용하는데, 예를 들어 항공기의 운항 경로를 최적화할 때도 사용하고 네트워크 분야에서도 많이 활용하는 개념이다.

 

이 MST를 구하는 대표적인 그리디 알고리즘으로는 프림 알고리즘, 크루스칼 알고리즘을 들 수 있다.

 

 

• 프림 알고리즘 (prim's algorithm) : 가중치가 최소인 "정점"부터 MST에 추가하는 알고리즘

1. 임의의 정점을 하나 선택해서 최소 신장 트리에 추가한다.

2. '최소 신장 트리와 연결되어 있는 정점들' 중 "가장 가중치가 적은 정점"을 MST에 추가한다.(여기가 greedy적 선택)
단, cycle을 형성하지 않는 정점을 추가해야 한다.

3. 과정 2를 신장 트리 조건에 만족할 때까지 반복한다.

 

• 크루스칼 알고리즘 (Kruskal algorithm) : 가중치가 최소인 "간선"부터 MST에 추가하는 알고리즘

1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.

2. 가중치가 낮은 간선부터 MST에 하나씩 추가한다. (이 부분이 greedy적 선택) 
단, cycle을 형성하지 않는 정점을 추가해야 한다.

3. 과정 2를 신장 트리 조건에 만족할 때까지 반복한다.

 

• 프림 vs 크루스칼 알고리즘 비교

	프림	크루스칼
알고리즘의 목적	MST(최소 신장 트리)	MST(최소 신장 트리)
시간 복잡도(정점 V, 간선 E)	O(E * logV) (인접 리스트 활용 시 O(N^2))	O(E * logV)
탐색 방법	임의 정점에서 최소 인접 가중치를 가지는 정점을 찾아 확장하는 방식	최소 가중치를 가지는 간선부터 하나씩 추가하는 방식
연결 요소	그래프 내의 모든 정점들이 반드시 연결되어야 함	연결되지 않은 그래프도 존재 가능

 

 

 

3. 배낭 문제 (knapsack problem)

- 배낭에 담을 수 있는 최대 무게가 존재하고, 무게와 가치가 다른 짐들이 있을 때 이 짐들을 잘 조합해서 배낭의 최대 무게를 초과하지 않으면서 담은 가치를 최대로 하는 문제

 

짐 A : [10kg, 가치 19]
짐 B : [7kg, 가치 10]
짐 C : [6kg, 가치 10]

배낭 : 15kg

 

위와 같이 짐 A, B, C가 있고 최대 15kg를 담을 수 있는 배낭이 있다고 해보자.

 

배낭 문제의 목표는 모두 '최대한 배낭에 높은 가치의 짐을 넣는다'이지만, 짐을 쪼갤 수 있는지 없는지에 따라 부분 배낭 문제와 0/1 배낭 문제로 나뉜다. 해당 조건에 따라 문제에 접근하는 방식이 달라지므로 두 방법을 모두 알아보자.

 

 

• 부분 배낭 문제 (짐 쪼개기 O) : fractional knapsack problem

부분 배낭 문제를 해결하려면 무게당 가치가 높은 짐을 최대한 많이 넣는 그리디 알고리즘을 사용하면 된다.

 

1. 짐 별로 무게당 가치를 구한다.

2. 무게당 가치가 높은 짐부터 넣을 수 있는 만큼 배낭에 넣는다.
	2-1. 배낭 용량이 짐 무게보다 크면 짐을 쪼개서 넣는다. 

3. 과정 2를 배낭이 허용하는 용량이 0이 될 때까지 수행한다.

 

 

실제로 위 알고리즘을 앞선 예제의 경우에 대입해보면 다음과 같다.

 

1. 무게당 가치를 계산

짐 A : [10kg, 가치 19]  -> 무게당 가치 : 19/10 = 1.9xx
짐 B : [7kg, 가치 10]   -> 무게당 가치 : 10/7 = 1.4xx
짐 C : [6kg, 가치 10]   -> 무게당 가치 : 10/6 = 1.6xx

 

 

2. 무게당 가치가 가장 높은 짐은 A이므로 A를 먼저 배낭에 넣는다. (배낭의 용량은 15kg이므로 모두 넣을 수 있음)

짐 A : [0kg, 가치 19]   -> 무게당 가치 : 19/10 = 1.9xx 
짐 B : [7kg, 가치 10]   -> 무게당 가치 : 10/7 = 1.4xx
짐 C : [6kg, 가치 10]   -> 무게당 가치 : 10/6 = 1.6xx

배낭 : 10kg/15kg

 

 

3. 그 다음으로 가치가 높은 짐은 C이다. 가용 용량이 이제 5kg이므로 C는 5kg만 넣는다.

짐 A : [0kg, 가치 19]   -> 무게당 가치 : 19/10 = 1.9xx 
짐 B : [7kg, 가치 10]   -> 무게당 가치 : 10/7 = 1.4xx
짐 C : [1kg, 가치 10]   -> 무게당 가치 : 10/6 = 1.6xx 

배낭 : 15kg/15kg

 

결과적으로 A, C를 배낭에 넣지만 C는 1kg이 남게된다.

 

 

이렇게 그리디 알고리즘으로 부분 배낭 문제를 풀 수 있다.

실제로 매 순간 짐을 선택하는 방식은 '무게당 가치'가 높은 짐이므로 최적 부분 구조를 만족한다.

그리고 짐을 쪼갤 수 있으니 앞에서 선택한 짐이 다른 짐 선택에 영향을 주지도 않으므로 그리디적 선택 요소에도 만족한다.

따라서 이 방식은 최적해를 보장한다고 할 수 있다!

 

 

• 0 / 1 배낭 문제 (짐 쪼개기 X) : 0/1 knapsack problem

이 문제는 짐을 쪼갤 수 없어서 지금 선택한 짐이 다음 짐 선택에 영향을 준다. 따라서 그리디 알고리즘을 적용하면 최적의 해를 구할 수 없으므로 최적의 해를 구하기 위해서는 동적 계획법으로 접근해야 한다. (0/1 배낭 문제는 그리디 알고리즘으로 '근사해'를 구할 수 있다고 얘기하기도 한다.)

 

실제로 그리디 알고리즘으로 풀 수 없는 이유를 앞선 예제를 통해 알아보자.

 

1. 무게당 가치가 높은 짐부터 넣는다. 그러면 A를 넣어야 하므로 이후 가용 용량은 5kg가 남는다. 이 상태에서는 짐을 쪼갤 수 없으므로 더 이상 넣을 수 있는 짐이 없다. 

짐 A : [10kg, 가치 19]  -> 무게당 가치 : 19/10 = 1.9xx (O)
짐 B : [7kg, 가치 10]   -> 무게당 가치 : 10/7 = 1.4xx
짐 C : [6kg, 가치 10]   -> 무게당 가치 : 10/6 = 1.6xx

배낭 : 10kg/15kg (가치 : 19)

 

2. 현재 배낭에 넣은 짐의 가치는 19이지만, 이 방법이 아닌 B, C를 넣었다면 더 높은 가치로 짐을 넣을 수 있었을 것이다.

짐 A : [10kg, 가치 19]  -> 무게당 가치 : 19/10 = 1.9xx 
짐 B : [7kg, 가치 10]   -> 무게당 가치 : 10/7 = 1.4xx (O)
짐 C : [6kg, 가치 10]   -> 무게당 가치 : 10/6 = 1.6xx (O)

배낭 : 13kg/15kg (가치 : 20)

 

 

이처럼 0/1 배낭 문제는 그리디 알고리즘으로 최적화 해를 구할 수 없다.

앞서 언급했듯 0/1 배낭 문제는 현재 짐의 선택이 다음 짐 선택에 영향을 주므로 그리디 알고리즘으로 풀 수 없기 때문이다. 

 

	부분 배낭 문제	0/1 배낭 문제
알고리즘 목적	배낭 속 짐들의 가치의 합이 최대가 되도록 함	배낭 속 짐들의 가치의 합이 최대가 되도록 함
문제 특징	짐을 쪼갤 수 있음	짐을 쪼갤 수 없음
시간 복잡도 (짐의 개수 N, 가치 W)	O(N*logN)	O(N*W)
그리디 적용 가능 여부	O	X

 

 

 

4. 그리디 알고리즘 예제 문제 (code)

 

1. 거스름돈 주기 

[문제 설명]
당신은 상점에서 계산을 마치고 거스름돈을 돌려 받아야 합니다. 다만 거스름돈을 최소한의 화폐 수로 받고 싶어졌습니다.
거스름돈 amount가 있을 때 화폐 단위 [1, 10, 50, 100]을 최소한으로 사용한 화폐 리스트를 반환하는 
solution() 함수를 반환하시오.

[제약 조건]
- 반환하는 값의 화폐 단위는 내림차순이어야 함
- amount는 자연수이다.
- 화폐 단위는 1, 10, 50, 100이며 화폐 개수는 무한이다.

[입출력 예시]
amount : 123 / return : [100, 10, 10, 1, 1, 1]
amount : 350 / return : [100, 100, 100, 50]

 

 

[문제 분석]

거스름돈 화폐 간의 관계가 서로 '배수 관계'라면 그리디 알고리즘으로 풀 수 있다. 쉽게 말해 10원 10장을 내는 것보다 100원을 1장 내는 것이 더 적은 화폐 수로 주는 방법이기 때문이다.

 

"앞에서 선택한 것이 뒤에 영향을 주지 않는다면 그리디 알고리즘을 사용할 수 있다"는 것을 명심하자!

따라서 이 문제도 그리디 알고리즘으로 풀어보자.

 

def solution(amount):
    denom = [1, 10, 50, 100]
    denom.sort(reverse=True) # 1. 화폐 단위를 큰 순서대로 정렬 : [100, 50, 10, 1]
    
    change = [] # 2. 거스름돈을 담을 리스트
    
    for coin in denom:
        while amount >= coin:   # 3. 해당 화폐 단위로 거스름돈을 계속 나눠줌
            change.append(coin) # 4. 거스름돈 리스트 업데이트
            amount -= coin      # 5. 정산이 완료된 거스름돈 빼기
    
    return change # 6. 거스름돈 리스트 반환

 

 

1. 거스름돈으로 주어진 금액을 최소 화폐 개수로 나타내기 위해 화폐 단위 [100, 50, 10, 1]을 큰 단위부터 차례대로 검사하려면 내림차순으로 정렬해야 한다.

2. change는 거스름돈을 담을 리스트이다.

3. 화폐 단위에 대해 현재 화폐 단위보다 크거나 같은 경우 계속 화폐 단위로 나누면서,

4. 현재 화폐 단위를 coin에 추가한다.

5. amount는 현재 화폐 단위만큼 빼는 것이다. 거스름돈 정산이 끝난 돈을 제거한다고 생각하면 된다.

6. 마지막으로 최소 화폐 리스트 change를 반환한다.

 

[시간 복잡도 분석]

N은 amount이다. 최악의 경우 모두 1원짜리 화폐만 사용할 수 있으므로 최대 N번 연산할 수 있다.

시간 복잡도 : O(N)

 

 

2. 부분 배낭 문제 

[문제 설명]
무게와 가치가 있는 짐 items와 배낭 wight_limit이 주어질 때 부분 배낭 문제를 푸는 solution() 함수를 작성하시오.

[문제 조건]
- weight_limit은 1 이상 10,000 이하의 자연수입니다.
- items의 길이는 1 이상 1,000 이하입니다.

[입출력 예시]
items : [[10, 19], [7, 10], [6, 10]] / weight_limit : 15 / return : 27.33
items : [[10, 60], [20, 100], [30, 120]] / weight_limit : 50 / return : 240

 

'''
부분 배낭 문제
1. 짐 별로 무게당 가치를 구한다.
2. 무게당 가치가 높은 짐부터 넣을 수 있는 만큼 배낭에 넣는다.
2-1. 배낭 용량 > 짐무게 인 경우 짐을 쪼개서 넣는다.
3. 과정 2를 배낭이 허용하는 용량이 0이 될때까지 수행한다.
'''

def calculate_value(items):
    for item in items:
        item.append(item[1] / item[0])
    return items

def sort_value(items):
    items.sort(key=lambda x : x[2], reverse=True)
    return items


def solution(items, weight_limit):  # [[10, 19], [7, 10], [6, 10]]
    items = calculate_value(items)  # [[10, 19, 1.9], [7, 10, 1.4], [6, 10, 1.6]]
    items = sort_value(items)       # [[10, 19, 1.9], [6, 10, 1.6], [7, 10, 1.4]]

    total_value = 0
    
    for item in items:
        weight = item[0]
        value = item[1]
        if weight_limit >= weight:
            total_value += value
            weight_limit -= weight
        else:
            fraction = weight_limit / weight
            total_value += value * fraction
            break
    return total_value

 

앞선 1번 예제인 거스름돈 주기 속 그리디 알고리즘을 반영하고, 여기에 배낭 문제에 필요한 '무게당 가치' 계산 메커니즘만 추가하면 완성할 수 있는 코드이다.

 

주석에 써놓은 알고리즘대로 구현을 하면 되는데,

1. 짐 별로 무게당 가치를 구한다. : calculate_value() 함수로 구현하여 items 리스트 수정

2. 무게당 가치가 높은 짐부터 넣을 수 있는 만큼 배낭에 넣는다. : sort_value() 함수로 구현하여 내림차순 정렬

사실 이 부분은 함수화를 하지 않아도 되지만 직관적 이해를 위해 분리하였다.

3. 짐들을 넣을 수 있는 만큼 배낭에 넣고, 용량을 초과한다면 쪼개어 넣는다. : solution() 함수 내에 if/else 문으로 조건을 분리하여 구현하였고, 쪼개어 넣는 부분의 로직은 fraction 변수에서 볼 수 있다시피 그냥 나눗셈으로 남은 부분을 소수점자리까지 계산하여 완벽히 메꾸도록 하였다.

 

[시간 복잡도 분석]

N은 items의 길이이다.

calculate_value()의 시간 복잡도는 O(N), sort_value()의 시간 복잡도는 O(NlogN), solution()의 시간 복잡도는 O(N)이므로,

최종 시간 복잡도 : O(NlogN)