그리디 알고리즘(탐욕법)은 현재 가장 좋아보이는 것을 고르는 방법을 의미한다.
그리디 알고리즘은 현재 가장 좋아보이는 것을 선택했을 때도 최적의 해가 나오는지 분석하는 것이 가장 중요하다.
거스름돈 문제
거스름돈으로 사용할 500원, 100원, 50원, 10원 짜리 동전이 무한하게 존재할 때 N원을 거슬러 줘야 한다면 거슬러 줘야 할 동전의 최소 개수를 구하세요. (단, N은 항상 10의 배수)
동빈나님 유튜브에 나오는 문제를 보고 직접 풀어본 코드는 다음과 같다.
내가 푼 풀이
#include <bits/stdc++.h>
using namespace std;
int change(int n){
int count = 0;
while(n >= 10){
if(n >= 500){
n -= 500;
count++;
continue;
}else if(n >= 100){
n -= 100;
count++;
continue;
}else if(n >= 50){
n -= 50;
count++;
continue;
}else if(n >= 10){
n -= 10;
count++;
continue;
}
}
return count;
}
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int a = change(1260);
cout << a << "\n";
return 0;
}동빈님의 문제 해석과 풀이 코드도 함께 확인해보았다.
거스름돈 문제의 경우 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러줄 수 있을 만큼 거슬러 주고 그 다음으로 큰 화폐로 또 같은 동작을 반복하면 된다.
가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해가 되는 이유는 동전 중 가장 큰 단위가 항상 가장 작은 단위의 배수이므로 다른 동전을 조합하더라도 최적의 해가 나올 수 없다.
(동빈님 코드 기준으로) 거스름돈 문제의 경우 시간 복잡도는 화폐의 종류가 K 일 때 O(K) 만큼의 시간 복잡도를 가진다고 한다. 동전의 총 종류에만 영향을 받기 때문에 금액과는 무관하다.
코멘트
나는 풀이의 "정당성" 부분에 대해서 고민하지 않고 풀었던 것 같다. 무작정 문제를 보고 풀기보다는 문제에 대한 정당성에 조금 더 고민해보고 푸는 습관을 들여야 겠다.
동빈님의 C++ 풀이 코드를 보니 굉장히 간결하고 짧았다.
아.. 나는.. C++ 문법을 잘 모르니까ㅠㅠ.. 라는 나름대로의 변명 하기에도 기초적인 배열이나 반복문, 나머지, 몫 연산, 출력 정도의 코드라서 문법을 몰라서 어쩔수 없네라고 하지도 못할 정도로 정말 간결하게 잘 짜셨다...!
cnt += n / coin;
n %= coin;동빈님 코드중에 동전으로 몫을 나눠서 동전 개수를 구하고 동전 크기 만큼의 나머지를 다시 n에 저장하는 코드를 보고 와 저렇게도 풀 수 있구나! 하고 하나 더 배울 수 있었다.
하지만 += 랑 %=는 무슨 말인진 알아도 코드 읽을 때는 넘나 해석하기 힘들어 하는 코린이라 cnt = cnt + (n / coin) 처럼 사용할 것 같지만....ㅋㅋㅋ 일단 새로운 풀이법을 알았다는 것에 만족...!!
나는 큰거로 뺄 수 있을 때까지 쭉 빼고 다음으로 넘어가는 다소 무식하면서 1차원적인(?) 방법으로 풀었는데 이런 방법이 있다니.. 열심히 배워서 문제를 까먹을 쯔음에 다시 도전해봐야겠다.
참고 자료
이코테 2021 그리디&구현
