[백준] 11047번, 1931번 - 그리디 알고리즘

그리디 알고리즘은 탐욕법이라고도 부르는데,

현재의 상황에서 최선을 선택하는 방법이다.

 

현재의 상황에서 최선을 선택하는 것이 항상 최선의 선택이라고는 볼 수 없는데, 왜냐하면

지금 말하면 마시멜로를 1개 주고 1분 뒤에 말하면  1개를 더 준다고 했을 때 최선의 방법은

1분 기다려서 2개 먹는 것이지만 그리디 알고리즘은 현재의 1개를 선택한다. 그래서 탐욕법이라고도 한다.

 

그리디 알고리즘을 사용하는 경우를 문제 2개로 나누어서 보겠다.

 

 

11047번 - 거스름돈을 낼 수 있는 최소 동전 개수 구하기 

 

거스름돈을 낼 수 있는 동전의 최소 개수를 구하는 법은 먼저 낼 수 있는 가장 큰 단위의 동전부터 내고 보는 법이다.

그래서 현재 낼 수 있는 가장 큰 단위의 동전을 내고 그 후에 그 다음 단위의 동전을 내고 하는 것을 반복한다.

 

1931번 - 가장 많은 강의를 할 수 있는 일정 짜기 

 

만약 여러개의 강의 스케줄이 있을 경우 가장 많이 강의를 하는 방법은 현재 가장 빨리 끝나는 강의를 시작으로 

그 강의와 겹치지 않는 시간에서 또 가장 빨리 끝나는 강의를 찾는 것을 반복하는 것이다.

 

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

int main() {	
	int N,time;
	cin >> N;
	vector<pair<int, int>> lecture;

	for (int i = 0; i < N; i++) {
		int s, f;
		cin >> s >> f;
		lecture.push_back(make_pair(f, s));
	}

	sort(lecture.begin(), lecture.end());//자동으로 pair의 first,second순 오름차순

	time = lecture[0].first;
	int count = 1;
	for (int i = 1; i < N; i++) {
		if (lecture[i].second >= time) {
			count++;
			time = lecture[i].first;
		}
	}
	cout << count;
}

 

algorithm 헤더의 sort는 pair을 매개변수로 넣을 경우에 자동으로 pair의 first를 기준으로 오름차순 정렬하고

first가 같다면 second 순으로 정렬한다. 위 코드에서는 first를 강의 종료시간 second를 강의 시작시간으로 입력했기 때문에 빨리 끝나는 강의 순서로 정렬하고 종료 시간이 같은 강의는 시작시간이 빠른 강의 순서로 정렬한다.