본문 바로가기

CS/Algorithm13

[알고리즘] Greedy Algorithm(탐욕 알고리즘) Greedy Algorithm[탐욕 알고리즘]이란? 각 단계에서 가장 최선의 선택지(가장 큰, 가장 작은 등)를 고르는 것. Greedy 알고리즘은 구현이 쉽다는 장점이 있지만, 항상 최선의 답을 구하는 것은 아니다. Greedy Algorithm을 활용 가능한 문제 1) 거스름돈 x라는 금액의 거스름돈이 주어야할 때, 10,000원, 5,000원, 1,000원, 500원, 100원으로 가장 적은 갯수의 거스름 돈을 주어야하는 상황 #include using namespace std; int main(){ int x, cnt = 0; cin >> x; // 가장 큰 액수의 화폐부터 선택 cnt += x / 10000; x = x % 10000; cnt += x / 5000; x = x % 5000; cn.. 2020. 1. 8.

티스토리툴바