그리디 알고리즘

 

그리디 알고리즘

현재상황에서 가장 좋아보이는 것만 선택하는 알고리즘

현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다 

 

사용하는 경우 

• 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제
• 시간 복잡도 O(N)이므로, 입력 범위가 크다 (1,000,000 < N)
• 어떤 기준에 따라 좋은 것을 선택하기 때문에 숨겨진 기준이 존재한다 → 정렬과 함께 사용될 가능성이 높음

 

특징

• 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제
• 창의력, 문제를 풀기 위한 아이디어를 떠올 릴 수 있어야 함
• 현재의 최적의 선택해 == 전체 문제의 최적의 선택해 가 되어야 함 
  • 모든 문제에서 정당한 해법이 아닐 수 있음 ( 현재 최적의 선택해 != 전체 문제의 최적해) 
  • 수학적 증명이 많이 필요함 (판단이 어려움)
  • 코딩 테스트는 주로 비슷한 유형/직관으로 판단가능 한 문제가 출제되므로 연습을 통해 감을 익혀야 함 

 

참고) 

다익스트라 알고리즘(최단경로) 는 엄밀히 그리디 알고리즘이다 

일단 문제를 만나면 그리디로 가능한지 생각해보고 아니라면 다이나믹, 그래프 알고리즘을 떠올려보자 

 

 

예시

예제 3-1 거스름돈

카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 "무한히 존재"한다고 가정한다.
손님에게 거슬러줘야할 돈이 N원 일 때, 거슬러줘야할 동전의 "최소 갯수"를 구하여라.
단, 거슬러 줘야할 돈 N은 항상 10의 배수이다.

using namespace std;

int coins[4] = {500, 100, 50, 10};


int main() {

    int n;
    cin >> n;

    int ans = 0;

    //시간 복잡도 : O(화폐의 가짓수) -> 최대 4번 작동함
    for(int idx=0; idx<4; idx++){
        ans += n/coins[idx];
        n = n%coins[idx];
        idx++;
    }


    cout << ans;
    

}

시간 복잡도는 O(화폐의 가짓 수)로 남아있는 거스름돈의 크기와는 무관하다 

 

순간의 최적해인 "가장 단위가 큰 동전부터 거슬러 주는 것"이 전체의 최적의 해가 될 수 있는 이유

가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수가 되기 때문에 큰 단위의 동전은 작은 단위의 동전들을 조합해 만들어 낼 수 있기 때문이다 (따라서 작은 단위의 동전을 선택할 경우 최소 갯수가 될 수 없음)

즉, 동전의 단위가 서로 배수 형태가 아니라 무작위인 경우에는 그리디를 사용할 수 없다 → 다이나믹 프로그래밍으로 해결 가능