[week6] 그리디 알고리즘

그리디 알고리즘 (탐욕법, Greedy Algorithm)

최적의 값을 구해야하는 상황에서 사용되는 근시안적인 방법론

'현재 상황에서 최적이라고 생각되는 것을 선택'해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘

단, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 목표로 하고 있음

 

그리디 해법은 그 정당성 분석이 중요하다. 

단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 

 

주로 문제를 분할 가능한 문제들로 분할하여 각 문제들에 대한 최적해를 구한 뒤,

이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다. 

 

[문제] 노드에서 가장 합이 높은 방법을 선택하기

 

각 상황에서 '최적'이라고 생각하는 방법을 선택 → 가장 높은 수를 선택

 

그리디 알고리즘은 이처럼 매 상황에서 가장 큰 값을 찾아가는 방식이다. 

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 

하지만, 코딩 테스트에서의 대부분의 그리디 문제는 탐욕적으로 얻은 해가 최적의 해가 되는 상황에서,

이를 추론할 수 있어야 풀리도록 출제된다. 

 

그리디 알고리즘의 주요 속성

문제를 풀 때 두 가지 조건이 성립해야 그리디 알고리즘을 적용할 수 있다. 

 

1. 탐욕 선택 속성 (Greedy Choice Property)

각 단계에서 '최선의 선택'을 했을 때, 전체 문제에 대한 최적해를 구할 수 있는 경우

즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것

 

2. 최적 부분 구조(Optimal Substructure)

전체 문제의 최적해가 '부분 문제의 최적해로 구성'될 수 있는 경우

즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적해를 구한 후

이를 조합하여 전체 문제의 최적해를 구하는 것을 의미

---

그리디 알고리즘 단계

1. 문제의 최적해 구조를 결정한다.
2. 문제의 구조에 맞게 선택 절차를 정의한다 : 선택 절차 (Selection Procedure)
3. 선택 절차에 따라 선택을 수행한다. 
4. 선택된 해가 문제의 조건을 만족하는지 검사한다 : 적절성 검사 (Feasibility Check)
5. 조건을 만족하지 않으면 해당 해를 제외한다. 
6. 모든 선택이 완료되면 해답을 검사한다 : 해답 검사 (Solution Check)
7. 조건을 만족하지 않으면 해답으로 인정되지 않는다. 

1단계 : 선택 절차 (Selection Procedure)

'현재 상태'에서 '최적인 선택'을 한다.

이 선택은 이후에는 바뀌지 않는다. 

 

2단계 : 적절성 검사 (Feasibility Check)

선택한 항목이 '문제의 조건'을 만족시키는지 확인한다. 

조건을 만족시키지 않으면 해당 항목은 제외된다. 

 

3단계 : 해답 검사 (Solution Check)

모든 선택이 완료되면, '최종 선택'이 '문제의 조건을 만족'시키는지 확인한다. 

조건을 만족시키면 해답으로 인정된다. 

---

그리디 알고리즘 vs 동적 계획법

분류	그리디 알고리즘 (Greedy Algorithm)	동적 계획법 (DP: Dynamic Programming)
설명	각 단계에서 최적의 선택을 하는 방식으로 문제를 해결	작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결하는 방식
성립 조건	1. 탐욕 선택 속성 (Greedy Choice Property) 2. 최적 부분 구조 (Optimal Substructure)	1. 중복 부분 문제 (Overlapping Subproblems) 2. 최적 부분 구조 (Optimal Substructure)
중복 부분 문제	중복 부분 문제를 해결하지 않습니다.	중복 부분 문제를 해결할 수 있습니다.
상황	각 단계의 상황에서 최적을 선택하여 최적의 경로를 구한다. 최적이 아닌 경우나 풀리지 않는 문제가 될 수 있음	모든 상황을 계산하여 최적의 경로를 구할 수 있다.  모든 상황을 계산하기에 시간이 오래 걸린다.

 

---

문제 예시 거스름돈

거스름돈으로 1260원을 거슬러줘야 할 때, 500원 100원 50원 10원짜리 동전이 무한정 존재한다면,

가장 큰 동전부터 가능한 많이 사용하는 방식으로 거스름돈을 계산해준다. 

 

그리디 알고리즘 적용

1. 선택 절차 : 거스름돈 문제에서 가장 가치가 큰 동전부터 선택한다. 
2. 적절성 검사 : 만약 선택된 동전의 가치가 거스름돈보다 크다면 다음으로 작은 동전을 선택한다. 
3. 해답 검사 : 합이 일치하면 거스름돈 문제가 해결된다. 

 

https://adjh54.tistory.com/212

[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기