Algorithm 공부 #10 - 그리디 알고리즘

 

Algorithm 공부 #10 - 그리디 알고리즘

 

 

그리디 알고리즘(Greedy Algorithm)

● 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘

● 동적 계획법보다 구현하기 쉽고 시간복잡도가 우수함

● 하지만 항상 최선의 해를 보장하지 못하기 때문에 전제 조건을 잘 살펴보아야 함

 

 

백준 11047번 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

※ 그리디 알고리즘 이용해서 문제 풀기 ※

● 배열의 마지막 인덱스부터 반복문을 돌리면서 A[i]가 K보다 작은 부분 찾아주기

● count에는 K를 A[i]로 나눈 몫을 더해주고 K는 K를 A[i]로 나눴을 때 나머지 값으로 갱신

 

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, K;
	cin >> N >> K;
	vector<int>A(N, 0);
	for (int i = 0; i < N; i++)
		cin >> A[i];

	int Count = 0;
	for (int i = N - 1; i >= 0; i--) {
		if (A[i] <= K) {
			Count += K / A[i];
			K %= A[i];
		}
	}
	cout << Count;
}

 

 

백준 1715번 카드 정렬하기

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

※ 그리디 알고리즘을 이용하되 우선순위 큐를 사용하기 ※

● 우선순위 큐를 사용할 때 내림차순 형태가 아니라 오름차순 형태로 변경해주기(최솟값부터 골라야하기 때문)

● 큐 사이즈가 1이 아닐 때까지 반복문 돌리기

● 결과값에 큐의 맨 앞과 두번째 값을 더해주고 더한 값들은 큐에서 pop해주고 더한 두 개의 값을 다시 큐에 푸쉬

 

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	priority_queue<int, vector<int>, greater<int>>pq;
	int data;

	for (int i = 0; i < N; i++) {
		cin >> data;
		pq.push(data);
	}

	int data1 = 0;
	int data2 = 0;
	int sum = 0;

	while (pq.size()!=1) {
		data1 = pq.top();
		pq.pop();
		data2 = pq.top();
		pq.pop();
		sum += data1 + data2;
		pq.push(data1+data2);
	}
	cout << sum;
}

 

 

 

백준 1744번 수 묶기

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	priority_queue<int>plusq;
	priority_queue<int,vector<int>,greater<int>>miusq;
	int zero = 0, one = 0;
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int data;
		cin >> data;
		if (data > 1)
			plusq.push(data);
		else if (data < 0)
			miusq.push(data);
		else if (data == 1)
			one++;
		else
			zero++;	
	}
	int result = 0;

	while (plusq.size() > 1) { //양수일 때, 큐의 사이즈는 다 빼내서 0이거나 하나가 남겨져서 1이 되거나 둘 중 하나임
		int data1 = plusq.top();
		plusq.pop();
		int data2 = plusq.top();
		plusq.pop();
		result += data1 * data2; // reuslt값 갱신
	}
	while (!plusq.empty()) { // 위 반복문에서 size가 1로 끝났을 때
		result += plusq.top(); // result값 갱신
		plusq.pop();
	}

	while (miusq.size() > 1) { // 음수일 때
		int data1 = miusq.top();
		miusq.pop();
		int data2 = miusq.top();
		miusq.pop();
		result += data1 * data2;
	}

	while (!miusq.empty()) { // 음수가 남아있을 때
		if (zero == 0) { // zero가 있다면 o과 곱해서 더할 필요가 없으므로 zero가 0일 때를 고려
			result += miusq.top();
		}
		miusq.pop();
	}
	result += one; // 마지막에 1의 개수 더해주기
	cout << result;
}

 

※ 그리디 알고리즘 + 우선순위 큐 사용 ※

● 입력받을 때 경우의 수를 4가지로( 1일 때, 0일 때, 1보다 클 때, 음수일 때)

● 0이 어디에 곱해지는냐에 따라서 최댓값이 달라지기 때문에 0의 개수를 따로 세주기

● 1은 양수와 곱하는 것보다는 양수에 1을 더하는 값이 더 크기 때문에 따로 세주기

● 음수는 우선순위 큐에 삽입하되 오름차순 형태로 바꿔서 두 개의 곱이 더 커지도록 해주기

● 양수는 그냥 우선순위 큐에 삽입

● 그 후 각 경우의 수에 따라서 그리디 알고리즘 실행

 

백준 1931번 회의실 배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

※ 그리디 알고리즘 + vector사용 ※

● 입력받는 값이 두 가지이므록 vector<pair<int,int>>로 선언해서 입력받기(입력받을 때 종료시간을 먼저 입력받기)

● 종료시간을 기준으로 vector정렬

● end값을 -1로 count를 0으로 초기화 한 뒤 N개만큼 반복문 돌리기

● A[i].second(시작시간)이 end보다 크거나 같다면 count++해주고 end를 A[i].first(종료시간)로 업데이트

● 종료 시간이 빠를수록 다음 회의와 겹치지 않는데 유리하기 때문에 이렇게 코드 작성

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	
	int N;
	cin >> N;
	vector<pair<int, int>>A(N);
	
	for (int i = 0; i < N; i++) {
		cin >> A[i].second;
		cin >> A[i].first;
	}

	sort(A.begin(), A.end());
	int sum = 0;
	int end = -1;

	for (int i = 0; i < N; i++) {
		if (A[i].second >= end) {
			end = A[i].first;
			sum++;
		}
	}
	cout << sum;
}

 

 

 

백준 1541번 잃어버린 괄호

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

※ 그리디 알고리즘 + vector사용 ※

● 최소값을 기준으로 하기 위해서는 입력받은 식에서 더하기를 모두 한 후 뺄셈을 해주는게 유리함

● 문자열로 입력받고 '-'를 기준으로 문자열을 분리

● 반복문을 돌려서 temp에 문자열을 더한 값을 저장(i==0이라면 맨 앞이므로 더해주고 나머지는 다 빼줌)

● 문자열 분리해주는 split함수, 문자열을 더해주는 mySum함수를 추가로 만들어주기

 

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

vector<string>split(string input, char delimiter);
int mySum(string n);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int answer = 0;
	string example;
	cin >> example;
	vector<string>str = split(example, '-');

	for (int i = 0; i < str.size(); i++) {
		int temp = mySum(str[i]);
		if (i == 0)
			answer += temp;
		else
			answer = answer - temp;
	}
	cout << answer;
}

vector<string>split(string input, char delimiter) {
	vector<string>result;
	stringstream mystream(input);
	string splitdata;

	while (getline(mystream, splitdata, delimiter))
		result.push_back(splitdata);
	return result;
}

int mySum(string n) {
	int sum = 0;
	vector<string>temp = split(n, '+');

	for (int i = 0; i < temp.size(); i++)
		sum += stoi(temp[i]);
	return sum;
}