"이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편 16장의 써머리입니다."

16. 그리디(Greedy)

1) 그리디 개념

문제 해결 과정에서 결정 순간마다 눈 앞에 보이는 최선을 선택, 그 선택 번복 X
⇒ 그리디 알고리즘은 지역 최적해를 추구한다

* 부분적으로 최적해를 구한다고 할 수 있어도 전체적으로 최선의 해를 구했는지는 불확실

그리디 알고리즘으로 거스름돈 내어주기

상황) 손님에게 8원을 거슬러 줘야 하는데 동전 종류가 5, 4, 1원만 있음, 이때 동전 개수를 가장 적게 만들기 위해 그리디 알고리즘 활용

1. 가장 값이 큰 동전부터 주기. 그리디 알고리즘은 현재 상황에서 최선의 선택을 하니 값이 가장 큰 동전부터 준다고 생각. → 5원부터 생각
   * 5원부터 거슬러 주는 선택은 이후 거스름돈을 주는 선택에 영향을 줌
2. 나머지 3원은 1원 3개를 주는 방법 → 총 4개의 동전으로 거스름돈을 줌
3. 이 방법은 최선은 아님. 4원 2개를 주는 것이 더 좋음 → 그리디 알고리즘은 가장 큰 값을 먼저 선택할 수 밖에 없음. 그래서 항상 최적의 해를 보장 X
   
   

그리디 알고리즘이 최적해를 보장하려면?

그리디 알고리즘은 특정한 상황에서 최적해를 보장, 이를 잘 활용하면 문제를 해결 가능

• 최적 부분 구조(Optimal Substructure) : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치
• 그리디 선택 속성(Greedy Selection Property) : 선택 과정이 다른 과정에 영향 없음
  
  

2) 최소 신장 트리

그리디 알고리즘을 사용하는 대표적인 트리 형태의 자료구조

신장 트리(Spanning Tree)란?

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

최소 신장 트리(Minimum Spanning Tree, MST)란?

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

경우에 따라 최소 신장 트리는 하나가 아닐 수도 있음

eg. 항공기의 운항 경로 최적화할 때 활용, 네트워크 분야에서 많이 활용

최소 신장 트리를 구하는 그리디 알고리즘

프림 알고리즘(Prim’s Algorithm)으로 최소 신장 트리 구하기

로버트 프림이 만든 알고리즘

1. 임의의 정점을 하나 선택해서 최소 신장 트리에 추가
2. 최소 신장 트리와 연결되어 있는 정점 중 가장 가중치가 적은 정점을 최소 신장 트리에 추가(그리디적 선택), 순환을 형성하지 않은 정점을 추가
3. 과정 2를 신장 트리 조건에 만족할 때까지 반복
   
   

크루스칼 알고리즘으로 최소 신장 트리 구하기

모든 간선을 가중치 기준으로 오름차순 정렬한다는 점 이외의 나머지 규칙은 프림 알고리즘과 동일

1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬
2. 가중치가 낮은 간선부터 최소 신장 트리에 하나씩 추가(그리디적 선택), 순환 형성 X
3. 과정 2를 신장 트리 조건에 만족할 때까지 반복
   
   

3) 배낭 문제(Knapsack Problem)

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

배낭 문제의 목표 - 최대한 배낭에 높은 가치의 짐을 넣는다

짐을 쪼갤 수 있는 부분 배낭 문제(Fractional Knapsack Problem)

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

1. 짐 별로 무게당 가치를 구하기
2. 무게당 가치가 높은 짐부터 넣을 수 있는 만큼 배낭에 넣기
   2-1. 배낭 용량이 짐 무게보다 크면 짐을 쪼개서 넣기
3. 과정 2를 배낭이 허용하는 용량이 0이 될 때까지 수행
   
   

짐을 쪼갤 수 없는 0/1 배낭 문제(0/1 Knapsack Problem)

이 문제는 짐을 쪼갤 수 없어서 지금 선택한 짐이 다음 짐 선택에 영향을 줌

그리디 알고리즘 적용 시 최적의 해 구할 수 없음(동적 계획법으로 접근 필요)

0/1 배낭 문제는 그리디 알고리즘으로 근사해를 구할 수 있다고 함

4) 몸 풀기 문제

문제 80) 거스름돈 주기

거스름돈 amount가 있을 때 화폐 단위 [1, 10, 50, 100]을 최소한으로 사용한 화폐 리스트를 반환

def solution(amount):
	lists = [100, 50, 10, 1]
	changes = []
	
	for c in lists:
		while amount >= c:
			changes.append(c)
			amount -= c

	return changes

assert solution(123) == [100, 10, 10, 1, 1, 1]
assert solution(350) == [100, 100, 100, 50]

5) 합격자가 되는 모의 테스트

문제 84) 귤 고르기

from collections import Counter

def solution(k, tangerine):
	cnt = Counter(tangerine)
	res, tot = 0, 0
  
	lists = sorted(cnt.values(), reverse=True)
  
	for count in lists:
		tot += count
		res += 1
  
		if tot >= k:
			break
  
	return res

assert solution( 6, [1, 3, 2, 5, 4, 5, 2, 3]) == 3
assert solution( 4, [1, 3, 2, 5, 4, 5, 2, 3]) == 2
assert solution( 2, [1, 1, 1, 1, 2, 2, 2, 3]) == 1