그리디 알고리즘

그리디 알고리즘

문제 해결 과정에서 단계마다 눈앞에 최선의 선택을 하고, 선택은 번복하지 않는다.

---

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

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

---

배낭 문제

부분 배낭 문제

짐을 쪼갤 수 있는 배낭 문제를 가정하자.

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

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

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

무게당 가치가 제일 높은 짐은 A이므로 먼저 10kg을 배낭에 넣는다.

그 다음으로 가치가 높은 짐 C를 5kg만 넣는다.

---

0/1 배낭 문제

짐을 쪼갤 수 없는 배낭 문제를 가정하자.

더 이상 짐을 쪼갤 수 없기 때문에 지금 선택한 짐이 다음 짐 선택에 영향을 미친다. 

따라서 그리디 알고리즘을 적용하면 최적의 해를 구할 수 없다.

최적의 해를 구하려면 dp로 접근해야 한다.

위와 같은 문제로 예를 들면, 무게당 가치가 높은 짐부터 넣을 시 A를 먼저 10kg 넣게 된다. 가용 용량은 5kg이 남고, 배낭에 넣은 짐의 가치는 19이다.

하지만 B, C를 넣었다면 더 높은 가치인 20으로 짐 13kg을 넣을 수 있다.

이처럼 그리디 알고리즘으로 구한 해가 최적의 해임을 보장하기 위해서는 현재 선택이 다음 선택에 영향을 미치지 않아야 한다.

---

그리디 vs 동적 프로그래밍

	그리디	동적 프로그래밍
문제 해결 방식	각 단계에서 현재 최적의 선택만 수행	부분 문제의 해를 저장하고 재활용하여 전체 문제 해결
최적해 보장	일부 문제에서만 최적해 보장	항상 최적해 보장
실행 속도	일반적으로 매우 빠름 O(n) 또는 O(n log n)	일반적으로 그리디보다 느림 O(n²) 이상
메모리 사용	매우 적음	중간~많음 (메모이제이션 테이블 필요)
적용 가능한 예시	• 거스름돈 문제 • 회의실 배정 • 크루스칼 알고리즘 • Fractional Knapsack	• 0/1 Knapsack • 최장 증가 수열(LIS) • 행렬 곱셈
성립 조건	• 최적 부분 구조를 가짐 (부분적인 최적해가 전체 최적해로 이어짐) • 이전 선택이 이후 선택에 영향을 주지 않음	• 최적 부분 구조를 가짐 • 중복되는 부분 문제가 존재
중복 부분 문제	중복 부분 문제를 해결하지 않음	중복 부분 문제를 해결할 수 있음
시간 복잡도 개선 가능성	제한적	메모이제이션으로 크게 개선 가능