[ 그리디(Greedy, 탐욕) ] 알고리즘 정리 및 문제

그리디(Greedy, 탐욕) 알고리즘

최적해를 구하는 데에 사용되는 근사적인 방법

항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.

이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

 

매순간마다 여러 경우 중 하나를 결정해야할 때, 그 순간에 최적의 경우를 선택해 나아가는  방식으로 최적인 해를 구한다.

하지만, 순간마다 하는 선택은 지역적으로는 최적이지만, 최종적(전역적)으로는 최적이라는 보장이 없다.

그렇기에 그리디 알고리즘을 사용하여 최종적으로 최적의 해를 구하려면 지역적으로 최적을 선택한 결과가 최종적으로도 최적일 수 있는 문제여야한다. 그러기 위해선 아래의 2가지 조건을 만족하는 문제여야한다.

 

그리디 알고리즘 적용 시, 최적해를 구할 수 있는 조건 (2가지)

a ) 탐욕스러운 선택 속성 ( greedy choice property )

      앞의 선택이 이후의 선택에 영향을 주지 않아야 한다.

 

b ) 최적 부분 구조 ( optimal substructure )

       매 순간의 최적의 해가 문제 전체에 대한 최적의 해여야 한다.

 

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다.

 

그리디 알고리즘 사용 방법

1) 선택 절차

      현재 상태에서의 최적의 해를 선택한다.

2) 적절성 검사

      선택된 해가 문제의 조건을 만족하는지 검사한다.

3) 해답 검사

      원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

 

그리디 알고리즘 특징

그리디  알고리즘을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 그리디 알고리즘은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다.

 

---

문제

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

1461번: 도서관

1461 풀이 코드 ⬇️

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

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

priority_queue<int> plusQue; // 내림차순
priority_queue<int, vector<int>, greater<int>> minusQue; // 오름차순
int n, m;

int PlusPops_UntilEmpty()
{
	int sum = 0;
	while (!plusQue.empty())
	{
		int n = plusQue.top();

		for (int i = 0; i < m; i++)
		{
			if (!plusQue.empty())
				plusQue.pop();
			else
				break;
		}
		sum += 2 * n;
	}
	return sum;
}

int MinusPops_UntilEmpty()
{
	int sum = 0;
	while (!minusQue.empty())
	{
		int n = minusQue.top();

		for (int i = 0; i < m; i++)
		{
			if (!minusQue.empty())
				minusQue.pop();
			else
				break;
		}
		sum += 2 * n;
	}
	return sum;
}

int main()
{
	freopen("input.txt", "r", stdin);
	
	cin >> n >> m;

	int farthest = 0;
	for (int idx = 0; idx < n; idx++)
	{
		int number;
		cin >> number;
		if (number > 0)
		{
			plusQue.push(number);
			
			if (abs(farthest) < number)
				farthest = number;
		}
		else
		{
			minusQue.push(number);
			
			if (abs(farthest) < abs(number))
				farthest = number;
		}
	}

	int result = 0;

	if (farthest > 0)
	{
		result += farthest;

		for (int i = 0; i < m; i++)
		{
			if(!plusQue.empty())
				plusQue.pop();
			else
				break;
		}

		result += PlusPops_UntilEmpty();
		result -= MinusPops_UntilEmpty();
	}
	else
	{
		result -= farthest;

		for (int i = 0; i <  m; i++)
		{
			if (!minusQue.empty())
				minusQue.pop();
			else
				break;
		}

		result -= MinusPops_UntilEmpty();
		result += PlusPops_UntilEmpty();
	}
	cout << result;
	return 0;
}

// 가장 먼 곳 부호 찾기
// 만약 해당 부호가 양수면, 양수쪽에서 처음에는 n%m개씩 pop. 첫번째pop만 1번 더해주고 
// m개씩 pop하고 첫번째pop수만 2번씩 더해주기

// -39 -37 -29 -28 -6 2 11
// 11 11 39 29 29 6 6

// -45 -26 -18 -9 -4 22 40 50
// 45 45 9 9 50

// -1 3 4 5 6 11
// 1 1 3 3 5 5 11