그리디

-1) 그리디 개념

그리디는 "탐욕스러운" 이라는 뜻

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

" 지역 최적해를 추구한다 "
-> 부분적으로 최적해를 구한다고 할 수 있지만 전체적으로 최선의 해인지는 확답 x

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

아래와 같은 특정한 상황에서 최적해를 보장하므로 이를 활용하면 문제를 잘 해결 가능
1. 최적 부분 구조 : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치
2. 그리디 선택 속성 : 선택 과정이 다른 과정에 영향을 주지 않음

평소에는 그리디 선택이 뒤의 선택에 제약을 주며 최적해를 구하지 못하게 하는 것

하지만,
그리디 알고리즘은 빠른 시간 내에 근사해를 제공하는 효율적인 방법 중 하나

---

-2 ) 최소 신장 트리 ( 그리디 알고리즘을 사용하는 예시 )

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

최소 신장 트리란? ( MST )
신장 트리 중 간선의 가중치 합이 최소인 트리
( 경우에 따라 최소 신장 트리는 하나가 아닐 수 있음 )

최소 신장 트리를 구하는 그리디 알고리즘에는 두 가지가 있음

• 프림 알고리즘
• 크루스칼 알고리즘

1. 프림 알고리즘으로 최소 신장 트리 구하기

" 임의 정점에서 최소 인접 가중치를 가지는 정점을 찾아 확장하는 방식"

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

2. 최소 신장 트리와 연결되어 있는 정점 중에서 가장 가중치가 적은 정점을 최소 신장 트리에 추가 ( 단, 순환을 형성하지 않는 정점을 추가해야 )

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

-> O(E*logV)

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

" 최소 가중치를 가지는 간선부터 하나씩 추가하는 방식"

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

2. 가중치가 낮은 간선부터 최소 신장 트리에 하나씩 추가 ( 단, 순환을 형성하지 않는 정점을 추가해야 )

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

-> O(E*logV)

---

-3) 배낭 문제 ( 그리디 알고리즘을 사용하는 예시 )

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

" 최대한 배낭에 높은 가치의 짐을 넣는다 "

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

매 순간 짐을 선택하는 방식은 무게당 가치가 높은 짐
그리고 짐을 쪼갤 수 있으니 앞에서 선택한 짐이 다른 짐 선택에 영향 x
-> 최적해 보장
-> O(NlogN)

짐을 쪼갤 수 없는 0/1 배낭 문제
짐을 쪼갤 수 없어서 지금 선택한 짐이 다음 짐 선택에 영향을 줌
-> 최적의 해 x ( 최적의 해 구하려면 동적 계획법으로 접근해야 )
-> O(N*W)