그리디 알고리즘

샤핑

 

 

이번 시간에는 그리디 알고리즘에 대해서 살펴보겠습니다.

 

 

 

그리디 알고리즘(Greedy Algorithm) - "가장 좋아보이는 것부터 찾아가자!"

- 지금 이 순간 당장 최적인 답을 선택해서 적합한 결과를 도출하는 기법입니다.

- '현재 가장 좋아보이는 것부터 찾아가는 기법'이라고 이해하면 됩니다. 위의 그림과 같이, 남자가 가장 예뻐보이는 여자부터 만나는 것을 떠올리면 됩니다 ㅋㅋㅋ

 

 

가장 대표적인 예시: 거스름돈 계산

거스름돈을 줄 때는 동전과 지폐의 수를 최대한 적게 해서 주는 것이 일반적입니다. 예를 들어, 500원을 거스른다고 하면, 500원짜리 하나만 주면 되지, 10원짜리 50개를 주지는 않잖아요? ㅋㅋ 이렇게 하려면, 가장 큰 금액부터 나누어나가야 합니다. 소스 코드는 아래와 같습니다.

 

 

출력 결과)

동전 및 지폐의 최소 개수:  3 개 

50000 원:  0 개
10000 원:  1 개
5000 원:  1 개
1000 원:  0 개
500 원:  1 개
100 원:  0 개
50 원:  0 개
10 원:  0 개

 

※ 거스를 돈(15500)을 가장 큰 금액(50000)부터 나누어나갑니다. 따라서, 50000으로 나누면 0이고, 10000으로 나누면 1입니다. 이러한 몫을 배열에 저장합니다. 그리고, 거스른 만큼 금액에서 제외해야 하므로, 값을 나눈 나머지를 대입합니다.

 

 

<출처>

나무위키: 그리디 알고리즘

소스 코드: https://github.com/jhs951101/Greedy