이것 저것 &

문제링크: https://www.acmicpc.net/problem/1339

간만에 풀어보는 그리디 알고리즘!

접근방식

1. 일반적인 접근방식으로 숫자 자릿수가 큰 경우에 높은 숫자를 배정해주면 될거라고 생각함

ex) accc + bbb일때,

a가 9가 되어야 하지요!

2.  다만 자릿수가 동일한 경우에 우선순위 배정을 신경써주야 한다!

ex) abbb + acdd

이때, a =9 는 당연하고 c와 b 중에서 b에 8을 배정해야 하는 부분!

이부분을 처리하기 위해서, 각 자릿수를 더해주는 형식으로 진행했다.

a = 1000 + 1000 = 2000b = 111 c = 100d = 22

숫자가 더 큰 친구가 높은 우선순위에 속하도록 구현하면 끝!~

문제풀이 

1.  문제 접근 2번에 설명한 것처럼 구현을 진행함

이때, 내림차순으로 정렬을 진행해두어야 함

2. 정렬된 값들을 순서대로 탐색하며 수를 배정해줌으로서 문제 해결

정답코드입니다.

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

int arr[26] = { 0, };
int n = 0;
int result = 0;

bool cmp(int& a, int& b) {
	if (a > b)
		return true;
	else
		return false;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;

		int cnt = 1;
		for (int j = temp.size() - 1; j >= 0; j--) {
			arr[temp[j] - 'A'] += cnt;

			cnt *= 10;
		}
	}

	sort(arr, arr + 26, cmp);
	int cnt = 9;
	for (int i = 0; i < 26; i++) {
		if (arr[i] == 0)
			break;

		result += arr[i] * cnt;
		cnt--;
	}

	cout << result << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/2812

수학적인 관점에서 생각해봐야 하는 그리디 문제였습니다. 

접근방식

1. 처음에는 단순히 arr[0], arr[1]만 비교해주고 값을 지워가면 되는 것으로 이해함

2. 근데 예외가 분명히 존재함

7 3

7654321

결과값은 7654

3. 뒤에 있는 값들도 함께 고려해야한다는 것을 알게됨

4. dequeue에 값들을 저장하고  뒤에 있는 값보다 작은 경우에는 dequeue에서 제외해주는 형태로 구현하자!

문제풀이 

1. 문자열의 이전 값(deque에 저장된) 들이 더 작다면 pop을 계속 시행, k값 감소

2. deque에 해당 문자열 삽입 

3. 출력할 때는 deq.size() - k만큼 출력

아래는 정답 코드

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

int n, k;
string val;
deque <char> deq;
int main() {
	iostream::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	cin >> val;

	for (int i = 0; i < val.length(); i++) {

		while (k && !deq.empty() && deq.back() < val[i]) {
			deq.pop_back();
			k--;
		}
		deq.push_back(val[i]);
	}


	for (int i = 0; i < deq.size() - k; i++) 
		cout << deq[i];
	
	cout << "\n";

	return 0;
}

문제링크: https://www.acmicpc.net/problem/1461

접근방식

1.  정렬을 하고, 문제를 해결해야함을 인지

2.  정렬을 하고 최선의 선택을 하며 결과를 도출하는 그리디임을 인지 

3.  양수, 음수별로 진행 -> m개씩 전달하는 값을 도출 -> 가장 먼 값은 왕복이 아님

문제풀이 

1. 2. 예시에서는 -37 2 -6 -39 -29 11 -28 -> -39 -37 -29 -28 -6 2 11

3.  {-39} {-37 -29} {-28 -6} {2 11} 이렇게 4번 진행하되 -39를 마지막에 도달하면 131이 나옴

4. 즉,  음수 양수 따로 진행하며,  m개씩 선택하고 왕복값을 저장해준다. 그리고 가장 극단 값에 있는 값을 빼줌 (왕복x)

그리디 알고리즘 문제였습니다.

아래는 정답코드입니다.

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

int n, m;
int arr[10001] = { 0, };
int pindex = 0;
int result = 0;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

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

	sort(arr, arr + n);
	
	for (int i = n - 1; i >= pindex; i -= m) {
			result += (arr[i]*2);
	}

	for (int i = 0; i < pindex; i += m) {
			result += abs(arr[i] * 2);
	}

	result -= max(abs(arr[0]), abs(arr[n - 1]));

	cout << result << endl;
	return 0;
}

문제링크: https://www.acmicpc.net/problem/1493

정렬을 하고 최선의 선택을 함으로써 결과를 도출하는 그리디 문제입니다.

처음에는 부피로 접근하여 문제를 해결하려고 했지만, 부피가 크다고 해당 범위를 채울 수 없는 것을 깨닭았습니다.

왜냐하면 한번 채운 상태인 부피의 모양이 사각형모양이 아닐 수 있기 때문입니다. 

문제해결하기위해서는 

분할정복 개념에 대해서 아셔야합니다.

저는 가장큰 박스로 채우고 나머지 부분을 재귀호출을 통해서 결과를 얻게끔 하였습니다. 

코드를 이해하시고 꼭 직접 작성해보세요.

정답코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
struct var{
	int a;
	int b;
};
bool cmp(var t1, var t2) {
	if (t1.a > t2.a) return true;
	return false;
}
int l, w, h, n;
int result = 0;
var arr[20];
bool jud = true;
void solved(int ll, int ww, int hh) {
	if (jud == false) return;
	if (ll == 0 || ww == 0 || hh == 0) return;

	for (int i = 0; i < n; i++) {
		if (ll >= arr[i].a && ww >= arr[i].a && hh >= arr[i].a && arr[i].b > 0) {
			arr[i].b--;
			result++;
			solved(ll, ww, hh - arr[i].a);
			solved(arr[i].a, ww - arr[i].a, arr[i].a);
			solved(ll - arr[i].a, ww , arr[i].a);
			return;
		}
	}

	jud = false;
}


int main() {
	cin >> l >> w >> h;
	cin >> n;
	int temp1, temp2;
	for (int i = 0; i < n; i++) {
		cin >> temp1 >> arr[i].b;
		arr[i].a = pow(2,temp1);
	}
	sort(arr, arr + n, cmp); // 내림차순 정렬

	solved(l, w, h);

	if (jud == false)
		cout << -1 << endl;
	else
		cout << result << endl;
}

문제링크:https://www.acmicpc.net/problem/1092

그리디 문제입니다.

항상 최선의 선택을 할 때 결과값이 도출되기 때문입니다.

해당 문제는 n 배열과 m 배열을 내림차순으로 정렬하고 순서대로 큰 짐을 먼저 옮겨주면 되는 문제였습니다.

못 옮기는 기준은 가장 센 크레인 (arr_n[0])이 가장 무거운 짐(arr_m[0]) 보다 작을 때 입니다.

그리고 일반 배열에 O(n*m)로 구현하시면 시간초과입니다. 

최악의 상황에 O(m*n*m) 이 되어 500,000,000로 5초가 걸리기 때문입니다.

정답코드입니다.

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

int arr_n[51] = { 0 };
vector <int> arr_m;
int n = 0, m = 0, result = 0;

bool cmp(int a, int b) {
	if (a > b)return true;
	return false;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr_n[i];
	cin >> m;
	int num = 0;
	for (int i = 0; i < m; i++) {
		cin >> num;
		arr_m.push_back(num);
	}

	sort(arr_n, arr_n + n, cmp);
	sort(arr_m.begin(), arr_m.end(), cmp);

	if (arr_n[0] < arr_m[0]) {
		cout << -1 << endl;
		return 0;
	}

	
	while (1) {
		result++;

		for (int i = 0; i < n; i++) {
			
			for (int j = 0; j < arr_m.size(); j++) {
				if (arr_n[i] >= arr_m[j]) {
					arr_m.erase(arr_m.begin() + j);
					break;
				}
			}
		}
	
		if (arr_m.size() == 0)
			break;
		
	}
	cout << result << '\n';

}

저는 벡터를 사용해서 짐을 뺄때마다 erase로 값을 지워주도록 구현하였습니다.

문제링크:https://www.acmicpc.net/problem/10825

그리디 알고리즘입니다. (사실 그리디라고도 할 수 없는 단순 정렬문제)

algorithm 라이브러리에 sort함수를 구현해 해결했습니다.

cmp는 오버라이딩 된 형태라 직접 구현할 수 있습니다. 

주석에 써놓은 번호순서대로 문제에서 요구하는 정렬을 구현한 것입니다. 

bool cmp(info a, info b) {
	if (a.korean > b.korean)  //1
		return true;
	else if(a.korean == b.korean){
		if (a.english < b.english) return true; //2
		else if(a.english == b.english){
			if (a.math > b.math) return true; //3
			else if(a.math == b.math) {
				if (a.name < b.name)return true; //4
			}
		}
	}

	return false;
}

처음에 시간초과가 났습니다. n = 100000 이고 sort 함수를 O(nlgn) 이기때문에 정렬의 문제는 아니였습니다. 

endl << 이 너무 많은 시간을 잡아먹어서 에러가 났었습니다. endl는 버퍼를 flush하는 역할을 겸하기 때문에 위 처럼 많은 출력을 해야해서 endl이 많이 사용될때는 endl사용을 지양하고 '\n'을 사용해야 합니다.

정답코드입니다.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct info {
	string name;
	int korean;
	int english;
	int math;
};

info arr[100001];
int n = 0;

/*
국어 점수가 감소하는 순서로
국어 점수가 같으면 영어 점수가 증가하는 순서로
국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)
*/
bool cmp(info a, info b) {
	if (a.korean > b.korean)  //1
		return true;
	else if(a.korean == b.korean){
		if (a.english < b.english) return true; //2
		else if(a.english == b.english){
			if (a.math > b.math) return true; //3
			else if(a.math == b.math) {
				if (a.name < b.name)return true; //4
			}
		}
	}

	return false;
}
int main() {

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i].name >> arr[i].korean >> arr[i].english >> arr[i].math;

	sort(arr, arr + n, cmp);

	for (int i = 0; i < n; i++)
		cout << arr[i].name <<'\n';

}

꼭 직접 작성해보시기 바랍니다:) 화이팅

문제링크:https://www.acmicpc.net/problem/8980

그리디 알고리즘 문제였습니다.

우선 첫번째로 조심하셔야 하는 점은 1.도착지 2.출발지 순으로 오름차순 정렬을 해줘야 한다는 것 입니다.

저는 항상 최선의 선택을 한다는 점에 너무 집중을 해서 1.출발지 2.도착지순으로 정렬을 해서 오답을 받았습니다. ㅠㅠ

이때 

4 40

3

1 4 40

2 3 40

3 4 40

과같은 입력이 들어오면 오답처리가 됩니다. (정상출력:80 오답:40)

1) 따라서 1.도착지 2.출발지 순으로 오름차순 정렬을 해야합니다.

2) 정렬 후 m번 반복하며 해당박스들을 받을 수 있는지, 얼마나 들어갈 수 있는지 확인합니다.

( 그러기 위해서는 해당위치에 박스를 얼마나 적재했는지 표시하는 int형 배열이 필요합니다.) -> capacity

3) 1. 시작도시부터 도착도시까지 가장 많이 적재된 박스양을 구합니다.

   2. 구한 값을 통해 해당도시에서 받을 수 있는 박스량 만큼 결과 값에 더해줍니다.

   3. 시작도시부터 도착도시까지 적재한 박스양을 capacity에 더해줍니다.

3)번과 같은 과정을 m번 반복하며 결과값을 결정하는 것입니다.

정답코드입니다. 꼭 직접 작성해보세요.

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

struct info {
	int sender;
	int reciever;
	int cnt;

	
};

info arr[10000];
int capacity[10001] = { 0 };
int n = 0, c = 0, m = 0;
int result = 0;

bool cmp(info a, info b) {
	if (a.reciever < b.reciever)return true;
	else if (a.reciever == b.reciever)
		if (a.sender < b.sender)
			return true;
		
	return false;
}

int main() {
	
	cin >> n >> c;
	cin >> m;

	for (int i = 0; i < m; i++)
		cin >> arr[i].sender >> arr[i].reciever >> arr[i].cnt;

	sort(arr, arr + m,cmp); //오름차순 정렬 1.도착지 2.출발지 

	for (int i = 0; i < m; i++) { 
		
		int maxcnt = 0;
		for (int j = arr[i].sender; j < arr[i].reciever; j++)  //보내는곳부터 받는곳까지
			maxcnt = max(capacity[j], maxcnt); //capacity의 최대값을 저장합니다. 박스를 얼마나 넣을 수 있는 확인하기 위해

		int val = min(arr[i].cnt, c - maxcnt);
		result += val;
		
		for (int j = arr[i].sender; j < arr[i].reciever; j++) {
			capacity[j] += val; // 이동되면서 해당 공간만큼 할당해주어야 박스가 못 실리겠죠
		}

	}

	
	cout << result << endl;

}

문제 링크: https://www.acmicpc.net/problem/1969

문제만 이해하면 그리디적인 개념으로 쉽게 풀 수 있는 문제였습니다.

모든 문자열에서 인덱스값들중 가장 큰 값만을 결과문자열로 저장하고 그값과 달랐던 값을 카운트해서 결과값을 도출하면 됩니다. 

문제 조건에서 사전순으로 가장 앞서는 것을 출력한다. 라는 규칙을 주의해서 풀어 주시면 됩니다. 

아스킷 코드값을 참조하며 arr[word[j][i] - 'A']++; 의 의미가 무엇인지, 그리고 arr[26]인지 생각해보세요.

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

int n, m;
string word[1000];
int result_sum = 0;
string result;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> word[i];
	


	for (int i = 0; i < m; i++) {
		int arr[26] = { 0 }, maxed = 0, max_index = 0;
		for (int j = 0; j < n; j++) {
			arr[word[j][i] - 'A']++; 
		}
		for (int j = 0; j < 26; j++) {
			if (maxed < arr[j]) maxed = arr[j],max_index = j;
		}
		result_sum += n - maxed;
		result += max_index + 'A';
	}

	cout << result << endl;
	cout << result_sum << endl;

}

화이팅:)