[Algorithm] 그리디

그리디란?

• 매 순간 최적이라고 생각되는 선택지를 선택하여 값을 구하는 방식
• 눈앞에 결과만 봄

• 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용

어떤 문제를 그리디로 풀어야할까?

다음 두가지 속성을 만족해야 그리디를 적용할 수 있다.

1. 탐욕 선택 속성
   1. 각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말합니다. 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것입니다.
2. 최적 부분 구조
   1. 전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’될 수 있는 경우를 말합니다. 즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미합니다.

💡 그리디와 dp의 차이

    dp의 속성은
    1.겹치는 부분 문제
    : 동일한 작은 문제들이 반복하여 전체의 문제와 겹친다.
    2.최적 부분 구조
    : 부분 문제의 최적결과가 전체에도 그대로 적용되어야 한다.
 
dp는 문제가 겹쳐서 이전 문제가 다음 문제에 영향을 끼치지만, 그리디는 영향 x

 

 

그리디 문제를 해결하는 방법

 

💡 선택 절차(Selection Procedure)란?

• 이 단계에서는 ‘현재 상태’에서 ‘최적인 선택’을 합니다.

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

 

 

💡 적절성 검사(Feasibility Check)란?

• 이 단계에서는 선택한 항목이 ‘문제의 조건’을 만족시키는지 확인합니다.

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

 

 

💡 해답 검사(Solution Check) 란?

• 이 단계에서는 모든 선택이 완료되면, ‘최종 선택’이 ‘문제의 조건을 만족’시키는지 확인합니다.

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

 

 

그리디 문제

그리디의 대표적인 문제로는 한화 거스름돈 문제!

거스름돈 문제

1. 선택 절차
   1. 가장 큰 동전부터 선택
2. 적절성 검사
   1. 현재 동전 > 남은 거스름돈 일 경우에는 다음으로 큰 동전 선택
3. 해답 검사
   1. 사용한 동전의 합이 거스름돈과 일치하면 해답 도출 완료!

💡 여기서 주의할 점은 한국 동전만 그리디로 풀고 센트는 dp로 풀어야 한다!

- 한국 동전은 배수로 이루어졌지만 센트는 아니라서 그리디로 풀게 된다면 나누어 떨어지지 않을 수 있음

 

주유소 문제

1. 선택 절차
   1. 한 블럭씩 비교하여 가장 저렴한 주유소를 minCost에 갱신한다.
   2. 첫 도시에서는 주유를 무조건 해야한다.
   3. minCost * 다음까지의 거리
2. 적절성 검사
   1. minCost > 현재 기름값일 경우 minCost를 갱신한다.
3. 해답 검사
   1. 최소를 찾는 문제라 여기선 해답검사 x