[Do it! 알고리즘 코딩테스트: Chapter 6. Greedy] Greedy Alogirthms

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

 

Greedy Algorithm

 Greedy Algorithm (탐욕 알고리즘)은 각 단계에서 가장 최적이라고 생각되는 선택을 반복하여 최종적인 해답을 구하는 방식이다.
즉, 현재 상태에서 가장 좋은 선택(Locally Optimal Choice)을 하면서 최종적으로 최적의 해(Solution)를 찾는 방법이다.

 

1. Greedy Algorithm 수행 과정

Greedy Algorithm은 다음과 같은 방식으로 동작한다.

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 처음으로 돌아가 같은 과정을 반복한다.

 Greedy Algorithm 은 미래를 고려하지 않고 현재 상태에서 가장 좋아 보이는 해를 선택하는 방식으로 동작한다.
따라서 일부 문제에서는 최적의 해를 보장하지 못할 수도 있다.

 

// Baekjoon Online Judge Problem. 11047

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, K;
	cin >> N >> K;

	vector<int> coins(N);

	for (int i = 0; i < N; i++)
		cin >> coins[i];

	int count = 0;

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

	cout << count;

	return 0;
}

 

 

// Baekjoon Online Judge Problem. 1715

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

int main() {
	int N;

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

	cin >> N;
	priority_queue<int, vector<int>, greater<int>> cards;

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

	int answer = 0;
	
	if (cards.size() == 1) {
		cout << 0;
		return 0;
	}

	while (cards.size() > 1) {
		int temp = 0;
		temp += cards.top();
		cards.pop();
		temp += cards.top();
		cards.pop();
		cards.push(temp);
		answer += temp;
	}

	cout << answer;
	return 0;
}

 

 우선 순위 큐 자료구조를 사용해 큐에 데이터를 삽입하면 자동으로 정렬되는 것이 핵심이였다. 문제에서 요구한대로 최솟값을 출력하려면 매시도마다 최솟값을 더하면 되는 Greedy 알고리즘이였다.

 단, cards.size() == 1일 경우에는 0을 출력해야한다는 함정이 있는 문제였다.

 

 

// Baekjoon Online Judge Problem. 1744

#include <iostream>
#include <vector>
#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> positive;
	priority_queue<int, vector<int>, greater<int>> negative;

	int num, one = 0, zero = 0;

	for (int i = 0; i < N; i++) {
		cin >> num;

		if (num == 1)
			one++;
		else if (num > 0)
			positive.push(num);
		else if (num < 0)
			negative.push(num);
		else
			zero++;
	}

	int answer = 0;

	while (!negative.empty()) { // negative
		if (negative.size() > 1) { // if there are more than 1 negative number
			int a = negative.top();
			negative.pop();
			int b = negative.top();
			negative.pop();
			answer += a * b;
		}
		else { // if there is only one negative number
			if (zero == 0) { // if there is no zero
				answer += negative.top();
				negative.pop();
			}
			else // if there is zero
				negative.pop();
		}
	}

	while (!positive.empty()) { // positive
		if (positive.size() > 1) { // if there are more than 1 positive number
			int a = positive.top();
			positive.pop();
			int b = positive.top();
			positive.pop();
			answer += a * b;
		}
		else { // if there is only one positive number
			answer += positive.top();
			positive.pop();
		}
	}

	answer += one;

	cout << answer;
	return 0;
}

 

 많은 조건 분기를 갖고 있는 문제였다. 

 

- 음수인 경우

  1. 우선 순위 큐의 size가 2보다 큰 경우 -> answer += a * b

  2. 우선 순위 큐의 size가 2보다 작은 경우

          (1) zero가 0인 경우 -> answer += a

          (2) zero가 0이 아닌 경우 -> answer += 0

 

- 양수인 경우

1. 우선 순위 큐의 size가 2보다 큰 경우 -> answer += a * b

2. 우선 순위 큐의 size가 2보다 작은 경우 -> answer += a

 

- answer += one

 

 

// Baekjoon Online Judge Problem. 1931

#include <iostream>
#include <vector>
#include <queue>
#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>> meetings(N);

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

	sort(meetings.begin(), meetings.end(), [](auto& a, auto& b) { // pair의 second로 내림차순 
		if (a.second == b.second) // 만약 second가 같다면 first로 내림차순
			return a.first < b.first;
		return a.second < b.second;
		});

	int count = 0;
	int num = 0;

	queue<pair<int, int>> q;
	q.push(meetings[0]);
	count++;

	while (!q.empty()) {
		pair<int, int> temp = q.front();
		q.pop();

		for (int i = num + 1; i < N; i++) {
			if (meetings[i].first >= temp.second) {
				q.push(meetings[i]);
				count++;
				num = i;
				break;
			}
		}
	}
	
	cout << count;

	return 0;
}

 

 

// Baekjoon Online Judge Problem. 1541

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

int main() {

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

	string str;
	cin >> str;

	int answer = 0;
	bool flag = false;
	string temp;
	

	for (int i = 0; i < str.size(); i++) {

		if (str[i] == '-') {
			if (flag == true) 
				answer -= stoi(temp);
			else
				answer += stoi(temp);
			flag = true;
			temp.clear();
		}
		else if (str[i] == '+') {
			if (flag == true)
				answer -= stoi(temp);
			else
				answer += stoi(temp);
			temp.clear();
		}
		else {
			temp.push_back(str[i]);
		}
	}

	if (flag == false) answer += stoi(temp);
	else answer -= stoi(temp);
	
	cout << answer;

	return 0;
}