Algorithm C++ [220118] :: Greedy - 1 (이것이 코딩테스트다 학습 정리)

Greedy 

:: 현재에서 지금 당장 좋은것만 고르는 방법

• Floyes-warshall
• Dijkstra

• 가장 큰 순서/ 가장 작은 순서 문제는 정렬 알고리즘을 사용 

---

[예제 3-1] 거스름돈(Greedy 기초문제)

문제

당신은 음식점의 점원. 카운터에는 거스름돈으로 500원/100/50/10원 동전이 무한히 존재한다고 가정. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구해라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

문제 해설

1. 가장 큰 화폐 단위부터 돈을 거슬러 주기 → 최소의 동전 개수로 모두 거슬러 주기 가능.

2. 화폐의 종류만큼 반복 수행해야 함.

3. 화폐의 종류가 K개일 경우, 위 소스코드의 시간 복잡도는 O(K)이다. n은 거슬러 줘야할 돈.

   즉, 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관

 

#include <iostream>
#include <string>
using namespace std;
int main() {
	int n = 1260;
	int cnt = 0;

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

	for (int i = 0; i < 4; i++) {
		cnt += n/coin_types[i]; // 해당 화폐로 거슬러 줄 수 있는 동전 개수 체크
		n %= coin_types[i];
	}
	cout << cnt << endl;
}

 

필독!

거스름돈 문제를 그리디로 해결할 수 있는 이유

⇒ 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문.

그리디는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답 도출 가능

실제로 거스름돈 문제에서 무작위로 단위가 주어진 경우에는 그리드로 해결 불가능. → 다이나믹 프로그래밍으로 해결 가능

 

 

---

난이도 '하' Greedy

[문제 1] 큰 수의 법칙 

#include <iostream>
#include <vector> 
#include <algorithm>  // sort() 사용

using namespace std;

int n, m, k;
vector<int> v;

int main() {
	// n, m, k 공백으로 입력받기
	cin >> n >> m >> k;

	// n개 수 공백 구분하여 입력받기
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v.push_back(x); // 뒤에 추가
	}
	
	sort(v.begin(), v.end()); // 입력 받은 수 정렬
	int first = v[n - 1]; // 가장 큰 수
	int second = v[n - 2]; // 두번째로 큰 수

	// 가장 큰 수가 더해지는 횟수 계산
	int cnt = (m / (k + 1)) * k;
	cnt += m % (k + 1);

	int result = 0;
	result += cnt * first; // 가장 큰 수 더하기
	result += (m - cnt) * second; // 두 번째로 큰 수 더하기

	cout << result << endl; // 최종 합
	
}

 

 

스토리 나열은 맞았는데 벡터 사용을 좀 더 고려하도록. 벡터 기초도 다시 다뤄야겠다. 그리고 sort() 정리하기 ㅜㅠ
내가 짠 코드는 비공개! 내일 전체적인 기초를 빠르게 훑어야겠다.