03: Greedy 알고리즘

개요

그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법.

정당성 분석이 필수.

코딩 테스트에서는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제된다.

 

문제1. 거스름 돈

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 손님에게 거슬러 줄 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구해라. 단, 거슬러 주어야 할 돈 N은 항상 10의 배수이다.

 

아이디어

가장 큰 화폐 단위부터 거슬러 주고, 다음으로 큰 화폐로 차례대로 거슬러 주면 최적의 해를 보장한다. 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이기 때문이다.

풀이:

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, cnt = 0;
	cin >> n;

	int coins[4] = { 500, 100, 50, 10 };
	for (int i = 0; i < 4; i++) {
		cnt += n / coins[i];
		n %= coins[i];
	}
	cout << cnt << "\n";
}

 

문제 2. 큰 수의 법칙

문제 

큰 수의 법칙이란 다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙

단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과할 수는 없음

 

입력 조건

첫째 줄에 N(2<=N<=1000), M(1<=M<=10000), K(1<=K<=10000)의 자연수가 주어지며 각 자연수는 공백으로 구분

둘째줄에 N개의 자연수가 주어짐. 각 자연수는 공백으로 구분. 단, 각각의 자연수는 1이상 10000이하의 수로 주어짐

입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

출력 조건

첫째 줄에 큰 수의 법칙에 따라 더해진 답을 출력

 

입력 예시

5 8 3

2 4 5 4 6 

 

출력 예시

46 

(* 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5  =  46)

 

아이디어 및 답지

// 3-2. 큰 수의 법칙
#include <iostream>
#include <algorithm>
using namespace std;

int n, m, k;
// 배열의 크기 n, 숫자가 더해지는 횟수 m, 연속해서 더해질 수 없는 횟수 k
int arr[1000] = {};
int main()
{
	cin >> n >> m >> k;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	// 2 4 5 4 6 // 6 6 6 5, 6 6 6 5 // n = 5, m = 8, k = 3
	// 3 4 3 4 3 // 4 4 4, 4 4 4, 4 // n = 5, m = 7, k = 2

	sort(arr, &arr[n]);
	int max_first = arr[n - 1];
	int max_second = arr[n - 2];

	int max_first_cnt = int(m / (k + 1)) * k + (m % (k + 1));
	int max_second_cnt = m - max_first_cnt; // **** 
	
	int result = 0;
	for (int i = 0; i < max_first_cnt; i++) {
		result += max_first;
	}
	for (int i = 0; i < max_second_cnt; i++) {
		result += max_second;
	}

	cout << result << "\n";
}

 

피드백

처음 풀 때는 아예 손도 못 대서 답지 보고 아이디어 얻었음. 두 번째로 풀 때는 두 번째로 큰 원소의 개수를 구하는 걸 못 했다.

 

 

 

 

문제 3. 숫자 카드 게임

 

 

문제 4. 1이 될 때까지

어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

 

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

 

예를 들어 N = 17, K = 4일 경우

1) 17 - 1 = 16

2) 16 // 4 = 4

3) 4 // 4 = 1

 

전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. 

 

내 풀이

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k, cnt=0;
	cin >> n;
	cin >> k;

	while (n != 1) {
		if ((n % k) == 0) {
			n /= k;
		}
		else {
			n -= 1;
		}
		cnt++;
	}
	cout << cnt << "\n";
}

 

답지

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k, result=0;
	cin >> n;
	cin >> k;
	
	while (true) {
		int target = (n / k) * k;
		result += (n - target);

		n = target;

		if (n < k)
			break;
		result++;
		n /= k;
	}
	result += (n - 1);
	cout << result << "\n";
}

 

 

 

기출 문제 1. 모험가 길드

한 마을에 모험가가 N명 있습니다. 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.
N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.

입력 예시

5
2 3 1 2 2

출력 예시

2

 

 

내 풀이

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	

	int cnt = 0, max = 0, cur = 0;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		if (max < num) {
			max = num;
		}
		cur++;
		if (max == cur) {
			cnt++;
			max = 0;
			cur = 0;
		}
	}
	
	cout << cnt << "\n";
}

 

답지 및 아이디어

공포도 기준으로 오름차순으로 정렬하면 항상 최소한의 모험가의 수를 포함하여 그룹을 결성할 수 있다. 앞에서부터 공포도를 확인하여 모험가의 공포도와 그룹에 결성된 모험가의 수를 비교하고 크거나 같다면 그룹으로 결성하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	vector<int> v;
	int num;
	cin >> num;
	v.push_back(num);

	sort(v.begin(), v.end());

	int cnt = 0, cur = 0;
	for (int i = 0; i < n; i++) {
		cur++;
		if (v[i] >= cur) {
			cnt++;
			cur = 0;
		}
	}
	cout << cnt << "\n";
}

 

답지 본 후 피드백

오름차순으로 해야 최소한의 모험가의 수, 즉 최대한의 그룹 수를 구할 수 있다.

 

 

 

기출 2. 곱하기 혹은 더하기

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

입력 예시1

02984

출력 예시1

576

입력 예시2

567

출력 예시2

210

 

내 풀이

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int arr[20] = {};
	string s;
	cin >> s;
	int length = s.length();
	for (int i = 0; i < length; i++) {
		arr[i] = s[i] - '0';
	}

	int result = arr[0];
	for (int i = 1; i < length; i++) {
		if (arr[i - 1] == 0) {
			result += arr[i];
		}
		else {
			result *= arr[i];
		}
	}
	cout << result << "\n";
}

 

답지 및 아이디어

대부분의 경우는 +보다 *가 값을 더 크게 만든다. 다만 두 수 중에서 하나라도 0이거나 1이면 더하기를 수행하는 것이 효율적이다.

#include <iostream>
using namespace std;
string str;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> str;

	long long result = str[0] - '0';

	for (int i = 1; i < str.size(); i++) {
		int num = str[i] - '0';
		if (num <= 1 || result <= 1)
			result += num;
		else
			result *= num;
	}
	cout << result << "\n";

}

 

답지 본 후 피드백

1도 검사해 주어야 한다. 불필요하게 for문을 두 번 돌렸다. 그래도 로직은 어느 정도 비슷하니까 장하다.