탐욕법

용어 정의

바로 다음 단계만을 봤을 때 최적해를 고르는 것.

탐욕법 패턴 (1) : 교환해도 악화되지 않음

x에 대한 함수 f(x)의 최적값을 찾으려고 한다. x를 약간 변형시켜 특정 조건 P를 만족하도록 만든 x’가 있을 때, f(x)보다 f(x’)가 더 적합하다면 조건 P를 만족하는 x들의 집합에 f(x)를 최적으로 만드는 x가 존재한다.

예시

구간 스케줄링 문제 N개의 일이 있다. i번째 일은 S_i에 시작해서 T_i에 끝난다. 최대 몇 개의 일을 끝낼 수 있는가?

typedef pair<int, int> Interval;
bool cmp(const Interval &a, const Interval &b){ // 종료시간 짧은거 우선으로 하게
	return a.second < b.second;
}
// N : 일 개수, S : 일 시작 시간 배열, T : 일 종료 시간 배열
// inter : S, T를 pair로 만든거
sort(inter.begin(), inter.end(), cmp);
int result = 0, cur_end_time = 0;
for(int i = 0; i < N; i++){
	if(inter[i].first < cur_end_time) continue;
	res++;
	cur_end_time = inter[i].second;
}
return res;

탐욕법 패턴 (2) : 현재가 좋으면 미래도 좋음

이번 단계 i를 최적화하면 다음 단계 i+1에서도 최적값이 나오고, 그게 끝까지 반복됨

예시

Multiple Array 문제 N개의 정수열 a, b와 N개의 버튼이 있다. i번째 버튼을 누르면 a₀, a₁, …, a_i 가 1씩 증가한다. a의 모든 요소가 같은 위치에 있는 b 요소의 배수가 되도록 만들려고 할 때, 최소 버튼 클릭 수는?

int pushBtn = 0;
for(int i = N-1; i >= 0; i--) {
	a[i] += pushBtn;
	int m = b[i] % a[i];
	if(m == 0) continue;
	else {
		pushBtn += (b[i] - m);
	}
 
}
return pushBtn;

참고자료

문제 해결력을 높이는 알고리즘과 자료 구조