[알고리즘]그리디(Greedy, 탐욕법, 욕심쟁이기법)

그리디 알고리즘이란?

탐욕알고리즘, 욕심쟁이기법 이라고도 합니다.

매순간 최적이라고 생각하는 해를 선택해나가서

최종적으로 최적해에 도달하는 알고리즘이라고 할 수 있습니다.

 

그렇게 때문에 구한 해가 항상 최적임이 보장되지는 않아서 근삿값을 구하는 용도로 사용되기도 합니다.

 

탐욕법이 충족되기 위한 조건

1. 앞의 선택이 이후의 선택에 영향을 주지않을 때
2. 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해일때

이렇게 2가지 조건을 만족할 때 그리디알고리즘이 잘 작용합니다.

이 조건들을 만족하지 못하면 최적해를 구하지 못하고 근삿값은 구할 수 있습니다.

 

개념자체만 봤을 때는 이해가 잘 안될 수 있으니 예제를 봅시다.

 

 

예제1 - 거스름돈(백준 5585번)

잔돈으로 500, 100, 50, 10, 5, 1엔이 있고

1000엔을 지불했을 때 가장적은 수의 거스름돈으로 지불하는 방법을 구하는 문제입니다.

 

예제 입력 - 380

예제 출력 - 4 (620 = 500+100+10+10)

 

가장 적은 수의 거스름돈을 지불하려면 가장 큰 단위의 잔돈을 우선으로 주면됩니다.

 

예제1 코드(c++)

#include <iostream>
using namespace std;

int main(void){
	int price; //물건 가격
	int coin[] = {500, 100, 50, 10, 5, 1}; //잔돈 종류
	int change = 0; //거스름돈 수

	cin>>price; //입력

	price = 1000 - price; //1000원 - 상품가격

	for(int i = 0;i<6&&price>0;i++){ 
		while(price>=coin[i]){ //줄 수 있는 큰 잔돈 뺌
			price -= coin[i];
			change += 1;
		}
	}
	cout<<change; 
}

이렇게 500. 100. 50... 의 잔돈처럼 각 잔돈들이 서로 배수인 경우에는 탐욕법으로 잘 풀립니다.

하지만 잔돈으로 만약 잔돈종류에 400원이 추가되었다면?

800원을 줘야한다면 500+100+100+100 보다 400+400이 더 효율적입니다.

이 경우에는 탐욕법보다 다이나믹 프로그래밍을 이용하면 최적해를 구할 수 있습니다.

 

suyeoniii.tistory.com/14

[알고리즘]다이나믹 프로그래밍(DP, 동적계획법)

 

예제2 - 회의실배정(백준 1931번)

겹치지 않도록 최대 회의 수를 출력하면됩니다.

 

여러 경우를 생각해볼 수 있는데요

 

• 먼저 시작하는 것부터 배정을 해주는 경우
  
  일찍 시작했지만 매우 늦게끝나는 경우가 있으므로 안됩니다.

 

• 가장 짧은 회의 시간을 가지는 경우
  
  시작시간과 종료시간을 덜 고려하기 때문에, 각 회의 사이의 공백이 다른 경우보다 길어질 수 있으므로 안됩니다.

 

• 일찍 끝나는 것부터 배정을 하는 경우
  
  일찍끝난다면, 그만큼 많은 회의들을 배정할 수 있으므로 가장 좋은방법이하고 할 수 있습니다.

-> 종료시간을 기준으로 정렬한 후 , 회의 시간이 겹치지 않게 배정하면됩니다.

 

예제2 코드(c++)

#include <iostream>
#include <algorithm> 
#include <vector>

using namespace std;

int main(){
	int N = 0; //회의 개수
	int start,end; //시작시간, 종료시간 입력
	int ans = 1; //가능 회의 개수 (답)
	int time; //회의 진행 시간
	vector<pair<int,int>>v; //순서쌍 벡터선언
    
    cin>>N;
	for(int i = 0; i<N; i++){ //입력
		cin>>start>>end;
		v.push_back(pair<int,int>(end, start)); //종료시간으로 정렬하기 위해 (종료시간, 시작시간)으로 할당
	}
    
	sort(v.begin(),v.end());//오름차순 정렬

	time = v[0].first; //time초기값 = 1번째 회의 종료시간
	
	for(int i = 1; i<N; i++){  //겹치지 않고 가능한 회의 수 계산
		if(time<=v[i].second){
			time=v[i].first;
			ans += 1;
		}
	}
	cout<<ans;
}

 

이 외에도 여러 문제를 풀어보며 감을 익히는 것이 중요할 것 같습니다!

감사합니다 :)