[알고리즘] Greedy

치치·2025년 1월 21일

알고리즘

알고리즘C++

목록 보기

12/24

그리디 알고리즘

최적의 해를 구하는 데에 사용되는 근사적인 방법
여러 경우 중 하나를 결정해야 할 때 마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답을 구하는 알고리즘이다

탐욕법 적용 조건

1. 탐욕 선택 속성

현재 단계에서 최적이라고 생각되는 선택이 결국 전체 문제의 최적 해로 이어지는 속성이다
이전의 단계가 현재 단계에 영향을 주지 않는 것
-> 즉, 각 단계에서 최적의 해를 선택해도 나중에 더 좋은 해를 구하는 데 방해되지 않고, 전체 문제의 최적의 해가 된다
예를 들면, 정수들의 합이 최대가 되는 해를 찾고싶다
-> 탐욕법은 각 단계에서 최적이라고 생각하는 해를 결정하니까, 각 단계의 최적의 해가 전체 문제의 최적의 해가 되는 문제에 사용하면 좋다!

-> 그리디를 사용하면 효율적인 답을 구할 수 없는 경우
: 탐욕법을 사용한 경우가 실제 최적의 해보다 안좋을 경우

즉, 탐욕 선택 속성을 만족하는 문제에서 탐욕법을 사용하여 최적의 해를 도출하는 데 효율적으로 사용할 수 있다

2. 최적 부분 구조

전체 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성된 문제구조이다
-> 부분 문제들에서 최적의 해가 될 요소를 선택하고 그것이 전체 문제의 최적의 해로 이어지기 때문에 이러한 문제에서 잘 사용될 수 있는 것
최적 부분 구조로 된 문제는 탐욕법 외에 분할정복, DP와 같은 알고리즘으로도 해결할 수 있다
-> 분할정복 : 재귀를 사용해 큰 문제 -> 작은 문제로 분할하여 해결한다 (부분 문제들로 큰 문제를 해결하게 됨)
-> DP(동적계획법) : 부분 문제의 해를 저장해뒀다가 큰 문제를 해결한다

그리디 알고리즘 단계

문제의 최적해 구조를 결정합니다.
문제의 구조를 맞게 선택 절차를 정의합니다. (선택절차)
선택 절차에 따라 선택을 수행합니다.
선택된 해가 문제의 조건을 만족하는지 검사합니다. (적절성 검사)
조건을 만족하지 않으면 해당 해를 제외합니다.
모든 선택이 완료되면 해답을 검사합니다. (해답 검사)
조건을 만족하지 않으면 해답으로 인정되지 않습니다.

거스름돈 문제

매개변수로 거슬러 줘야 할 돈의 금액 n을 받는다
탐욕법을 사용하여 잔돈 1000, 500, 100, 50, 10 원을 가장 적은 수 만큼 거슬러 주는 법을 구하는 문제이다

만약 1370원을 거슬러 줘야한다면 잔돈 액수 중 가장 큰 금액부터(최적의 답) 하나씩 카운트를 센다

while문을 사용하여, 각 잔돈을 카운팅한 방식

상수참조(const &) 타입으로 count 값을 반환한다

#include <iostream>
using namespace std;

const int& Greedy(int n)
{
	int count = 0;

	// 1. while문

	while (n >= 10)
	{
		if (n >= 1000)
		{
			n -= 1000;
			count++;
		}
		else if (n >= 500)
		{
			n -= 500;
			count++;
		}
		else if (n >= 100)
		{
			n -= 100;
			count++;
		}
		else if (n >= 50)
		{
			n -= 50;
			count++;
		}
		else if (n >= 10)
		{
			n -= 10;
			count++;
		}
	}
	return count;
}
int main()
{
#pragma region 탐욕법
	
    cout << "잔돈의 갯수는 : ";
	cout << Greedy(1370);

#pragma endregion

	return 0;
}

int 타입의 함수기 때문에, int로 값을 반환해야한다
-> 여기서는 int타입의 count값을 상수참조 타입으로 반환하였다

결과값 : 1000 1개, 100 3개, 50 1개, 10 2개

배열을 사용하여 잔돈을 배열에 넣고 하나하나 계산한 방식

#include <iostream>
using namespace std;

const int Greedy2(int n)
{
	int array[5] = { 1000, 500, 100, 50, 10 };

	int count = 0;

	for (int i = 0; i < 5; i++)
	{
		count += (n / array[i]);

		n -= (array[i] * (n / array[i]));
	}
	return count;
}

int main()
{
	cout << "거스름돈의 갯수 : " << Greedy2(1370);
}

결과값 :

한번 더 구현하기 (조금 다른 방법)

거스름돈을 넣은 배열을 벡터로 만들어봤음

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

const int Greedy2(int n)
{

	vector<int> array = { 1000, 500, 100, 50, 10 };
	int count = 0;

	for (int i = 0; i < 5; i++)
	{
		count += n / array[i];

		n -= array[i] * (n / array[i]);
	}
	return count;
}