[CH3 그리디] 당장 좋은 것만 선택하는 그리디

그리디 알고리즘(Greedy Algorithm)

• 단순하지만 강력한 문제 해결방법이다
• '탐욕법' 혹은 '욕심쟁이 알고리즘'으로도 불린다
• 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 -> 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 이후 미칠 영향은 고려하지 않는다!
• 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다

 

---

 

책의 예시와 비슷한 문제를 백준에서 풀어보자!

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

문제

이는 책의 예시 3-1(거스름돈)의 방식을 약간만 변형하여 C++로 구현하였다!

 

아래는 내가 구현한 코드이다

#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
    int n;
    int count=0; //동전 개수
    int coinArr[6]={500,100,50,10,5,1};

    cin>>n;
    n=1000-n;

    for(int coin : coinArr)
    {
        count+=(n/coin);
        n%=coin;
    }
    cout<<count;
    return 0;
}

문제에서는 1000엔 중 입력 받은 물건의 가격을 제외한 거스름돈을 반환하기 때문에 n을 입력 받고 1000에서 뺀 값을 다시 n에 저장하여 거스름돈을 계산하였다.

coinArr에 동전의 종류를 큰 순서대로 저장하고 반복문을 통해 큰 가격부터 차례대로 계산한다(이래야 가장 적은 동전의 개수를 반환할 수 있음)

반복문은 배열의 범위를 활용하였는데, 저런 식으로 쓰면 배열의 크기만큼 자동으로 반복문을 통해 접근하고, 현재 반복문에서 사용하는 요소는 coin 이라는 선언한 변수에 넘겨진다. 이를 활용하여 반복문 내에서 코드를 구현하면 된다.

따라서 나는 coin으로 거스름돈을 나눈 몫이 곧 해당 동전으로 거슬러줄수 있는 동전의 개수니까 이를 count에 더해주고 나머지 값을 다시 n에 저장하여 남은 금액을 다음 동전으로 다시 계산한다

책의 방식대로 쉽게 풀 수 있었다!

그리디 알고리즘은 어렵지 않지만, 문제가 그리디 알고리즘을 활용하는 것인지 판별하는게 어려운 것 같다,,,

이 문제에서는 '가장 적게'라는 키워드가 있어서 알 수 있었다!

더 많이 풀어보면서 몸에 익히면 되겠지!!

 

---

그리디 알고리즘의 정당성

• 그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 있는 것은 아니다
• 대부분의 문제는 이 알고리즘을 통해 '최적의 해'를 찾을 수 없을 것이다
• 하지만 위의 문제처럼 탐욕적으로 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다!
• 그리디 알고리즘으로 문제의 해법을 찾은 경우에는 그 해법이 정당한지 검토해야 한다
• 거스름돈 문제가 그리디 알고리즘으로 풀 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다!
  • 만약 거스름돈이 800원이고 화폐 단위가 (500, 400, 100)인 경우라면?
    • 그리디 알고리즘의 결과 : 4개 (500, 100, 100, 100)
    • 실제 최적의 해 : 2개 (400, 400)
• 따라서 대부분의 그리디 알고리즘 문제에서는 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 도출할 수 있다
• 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자!
• 만약 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 해결할 수 있는지 다시 고민해보는 것도 방법이다