chp16 그리디 (Greedy)

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

 

 

 

 

 

 

그리디: 매 현재 순간에 번복 없이 하는 최선의 선택

 

유명 예제 거스름 돈) 손님에게 8원 거슬러주는데 종류가 5, 4, 1원이고 동전 개수 최솟값 만드려면?
-> 큰 동전부터 주기? (5원1개, 1원 3개?)  

-> 사실 4원 2개하면 개수가 더 줄어듦

-> 그리디 알고리즘이 최적 해를 보장하지 못하는 이유

 

 

[그리디 최적해 보장 조건]:

1) Optimal substructure (최적 부분 구조): 부분 해 푸는 과정 = 최적해 구하는 과정

2) Greedy selection property(그리디 선택 속성): 선택 과정이 다른 과정에 영향 X

 

-> 결국 거스름돈 예제에서 오류 난 이유는 이 두 조건들 때문!

부분 해인 5원 선택의 제약으로 최적 해를 구하는데 방해가 되고 뒷 선택에 영향을 줌

 

(point!)

그리디 알고리즘은 만능은 아니지만 이 두 조건에 맞는 경우 그리디 알고리즘이 시간 단축에 도움을 줌!

 

 

 

대표 예제1> 최소 신장 트리(spanning tree): 모든 정점이 간선으로 연결되고 간선 개수가 정점 개수보다 하나 적은 그래프

 

최소 신장 트리 구하는 알고리즘은 2가지가 있다.

 

1) 프림 알고리즘(prim's algorithm):

임의 정점 선택 -> 최소 신장 트리에 추가 -> 순환이 생기지 않는 최소 신장 트리와 연결된 min(가중치) 정점을 최소 신장 트리에 추가(그리디), 그리고 신장 트리 조건에 맞을 때까지 계속 반복

 

2) 크루스칼 알고리즘: 그래프 모든 간선 가중치 기준 오름차순 정렬 -> 순환이 생기지 않는 min(가중치) 간선부터 최소 신장 트리에 하나씩 추가(그리디), 그리고 신장 트리 조건에 맞을 때까지 계속 반복

 

두 알고리즘의 중요 차이점: 크루스칼 알고리즘은 모든 간선을 가중치 기준으로 오름차순 정렬한다는 차이점(프림은 없음)

나머지는 같음!

 

 

 

 

 

 

 

대표 예제2> 배낭 문제= 냅색 문제(knapsack problem)

조건: 배낭에 담을 수 있는 최대 무게 제한 有, 무게와 가치가 다른 짐들 有  

목적: 무게 초과하지 않으면서 담은 가치 최대로 하는 문제 

기본 접근 방법: 배낭과 짐을 정의하고 시작하고 배낭 속 짐들 가치가 최대가 되도록 고민하기

 

1) 짐을 쪼갤 수 있는 경우(fractional knapsack problem): 무게당 가치가 높은 짐을 최대한 많이 넣는 그리디 알고리즘 적용

O(n log N) 시간 복잡도 나옴

 

2) 짐을 쪼갤 수 없는 경우(0/1 knapsack problem): 짐을 쪼갤 수 없음 -> 현재의 짐 선택이 다음 짐 선택 영향 有 

-> 그리디 적용 불가 (최적은 아니여도 근사 해는 가능할 수 있음)

-> 동적계획법(DP) 사용. 시간복잡도 O(N)