Chapter 10 - Greedy 탐욕법

이론 설명

1. Greedy 알고리즘은 현재 주어진 상황에서 가장 이득이 되는 최선의 경우를 선택하는 알고리즘을 의미한다.

2. Greedy 알고리즘은 지금의 선택이 앞으로 남은 선택들에 대해 어떤 영향을 끼칠지 고려하지 않는다.

3. Greedy 알고리즘은 최적해를 구하는 알고리즘이 아니다.

   1. 단, greedy가 최적해를 나타내는 경우의 수가 존재한다. 이 경우 bruteforce, dp보다 훨씬 빠른 속도와 적은 메모리로 최적해를 구할 수 있다는 장점이 있다.
   2. Greedy가 최적해를 나타내는 경우, 반드시 알고리즘의 정당성을 증명하는 과정을 거쳐야 한다.

4. Greedy 알고리즘 정당성 증명

   1. Greedy choice property(탐욕적 선택 특성): Greedy 방식으로 선택했을 때 손해볼 일이 없다는 것을 증명함.
   2. Optimal substructure(최적 부분 구조): 부분 문제에서 greedy 방식을 선택해서 구한 최적해가 전체 문제에 대한 최적해임을 증명함.

Ex 01 - 출전 선수 정하기 (MATCHORDER, 下)

• [전략 1] - 승수를 최대화하기 위해서는 상대편 선수보다 우리편 선수가 rating이 높은 선수들 중 가장 rating이 낮은 선수를 내보내는 것이 최선이다.

• [전략 2] - 상대편 선수의 rating이 모든 우리편 선수보다 높을 경우, 우리편의 가장 낮은 rating을 가진 선수를 내보내는 것이 최선이다.

• 근데 정말 이게 최선(greedy)일까? 이 전략들로 최적해를 구할 수 있을까? -> 정당성 증명!!

  1. greedy choice property

     • 전략 1의 경우

       • 만일 가장 rating이 낮은 선수 말고 다른 선수를 내보내는 최적해가 존재한다면?

       • 러시아	2,000	x	1,900
         한국	B	A	2,000

       • B > A이고 A가 한국의 가장 낮은 rating을 가진 선수라고 생각해보자. 2000 vs B는 B의 승리이고, x vs A는 승부 결과를 알 수 없다.

       • 이제, A와 B를 바꾼다고 가정해보자 (우리가 세운 가설대로)

       • 2000 vs A의 승부 결과를 알 수 없다. 그러나 x vs B는 B의 승리일 것이다. 즉, 최적해는 그대로다. 이 말은 곧 greedy 방식을 택해도 우리가 손해볼 일은 없다는 것이다!

     • 전략 2의 경우

       • 만일 가장 rating이 낮은 선수 말고 다른 선수를 내보내는 최적해가 존재한다면?

       • 러시아	999,999	x	1,900
         한국	B	A	2,000

       • B > A이고 A가 한국의 가장 낮은 rating을 가진 선수라고 생각해보자. 999,999 vs B는 상대팀의 승리이고, x vs A는 승부 결과를 알 수 없다.

       • 이제, A와 B를 바꾼다고 가정해보자 (우리가 세운 가설대로)

       • 999,999 vs A의 승부도 상대팀의 승리다. 그러나 x vs B는 결과를 알 수 없다. 즉, 최적해는 그대로다. 말은 곧 greedy 방식을 택해도 우리가 손해볼 일은 없다는 것이다!

  2. Optimal substructure

     • 매 경우 최선의 선택을 한다고 가정할 때, 우리가 손해볼 것이 없다는 것을 자명하게 알 수 있다.
  • 그러므로 greedy 방법을 택하는 것이 최적해를 이끄는 과정과 동일하다는 것을 알 수 있다.

• 코드를 작성해보자

  •   #include <iostream>
      #include <vector>
      #include <set>
      #include <algorithm>
      using namespace std;
      
      static int C, N;
      int solve(const vector<int>& rus, const vector<int>& kor) {
      	int ret = 0;
      	multiset<int> ratings(begin(kor), end(kor));
      	for (int rusIdx = 0; rusIdx < N; ++rusIdx) {
      		if (*ratings.rbegin() < rus[rusIdx])
      			ratings.erase(begin(ratings));
      		else {
      			ratings.erase(ratings.lower_bound(rus[rusIdx]));
      			ret++;
      		}
      	}
      	return ret;
      }
      
      int main() {
          ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
      
      	cin >> C;
      	while (C--) {
      		cin >> N;
      		vector<int> rus(N), kor(N);
      		for (int i = 0; i < N; ++i) cin >> rus[i];
      		for (int i = 0; i < N; ++i) cin >> kor[i];
      
      		cout << solve(rus, kor) << '\n';
      	}
      }

  • 요소의 중복을 허용하고 트리 구조로 자료를 저장하는 multiset stl 컨테이너를 사용해서 한국 선수를 레이팅 순으로 정렬해서 저장한다.

  • 첫 번째 if문은 필패하는 경우의 수를 의미한다. 필패하는 경우 가장 낮은 레이팅을 가진 선수를 내보내는게 최선이다.

  • 두 번째 else문은 이기는 경우를 의미한다. 이기는 경우 이길 수 있는 선수 중 가장 낮은 레이팅을 가진 선수를 내보내는게 최선이다.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    static int C, N;
    int solve(vector<int>& rus, vector<int>& kor) {
    	int ret = 0, size = rus.size() - 1;
    	sort(begin(rus), end(rus));		// 러시아 선수 레이팅 순 정렬
    	sort(begin(kor), end(kor));		// 한국 선수 레이팅 순 정렬
    	
    	while (rus[size] > kor.back()) size--;	// 필패하는 경우 카운트
    	int startKorIdx = N - size - 1;			// 최소 rating 선수를 제외한 시작 인덱스값
    
    	for (int korIdx = startKorIdx, rusIdx = 0; korIdx < N; ++korIdx) {
    		if (rus[rusIdx] <= kor[korIdx]) {	// 이기는 경우
    			rusIdx++;						// 다음 선수와 비교하기 위해 증가
    			ret++;							// 승수 증가
    		}
    	}
    	
    	return ret;
    }
    
    int main() {
        ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    
    	cin >> C;
    	while (C--) {
    		cin >> N;
    		vector<int> rus(N), kor(N);
    		for (int i = 0; i < N; ++i) cin >> rus[i];
    		for (int i = 0; i < N; ++i) cin >> kor[i];
    
    		cout << solve(rus, kor) << '\n';
    	}
    }

    • multiset이나 heap이 직관적이지 않다면 사용하지 않는 방법도 있다. 이 방법이 위의 방법보다 연산 횟수도 적고 빠르며 직관적이다.

Ex 02 - 도시락 데우기 (LUNCHBOX, 下)

• 어떤 순서로 도시락을 데우던지간에 일단 모든 도시락을 데워야 하므로 최소 sum(모든 도시락 데우는 시간)은 소요된다.

• 그러므로 결과에 영향을 주는 것은 마지막에 데우는 도시락을 먹는데 걸리는 시간 이다.  따라서 먹는데 오래걸리는 도시락 먼저 데우는 것이 최선임을 알 수 있다.

• 정말 그게 최선일까?? (정당성 증명)

  1. greedy choice property

     • 먹는데 가장 오래걸리는 도시락을 제일 먼저 데우는 것 말고 다른 최적해가 존재한다고 가정하자.
     • 점심시간 소요시간 = sum(모든 도시락 데우는 시간 + 먹는데 가장 오래걸리는 도시락 먹는 시간)이다.
     • 이번에는 가장 먼저 데우는 도시락과 먹는데 가장 오래걸리는 도시락 순서를 바꿔보자.
     • 점심시간 소요시간은 위 식보다 오래걸릴 수 없다. 즉, greedy 방식을 택해도 우리가 손해볼 일은 없다는 것이다!

  2. Optimal substructure

     • 매 경우 최선의 선택을 한다고 가정할 때, 우리가 손해볼 것이 없다는 것을 자명하게 알 수 있다.

     그러므로 greedy 방법을 택하는 것이 최적해를 이끄는 과정과 동일하다는 것을 알 수 있다.

• 코드를 작성해보자

  #include <iostream>
  #include <vector>
  #include <algorithm>
  using namespace std;
  
  static int C = 0;
  
  int solve(vector<pair<int, int>>& vec) {
  	// 먹는 시간이 긴 순으로 정렬함
  	sort(vec.begin(), vec.end(), [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});
  	int ret = 0, beginEat = 0;
  	for(const auto& time : vec) {
  		beginEat += time.first;	// 현재시간 + 데우는 데 걸리는 시간
  		ret = max(ret, beginEat + time.second);	// 먹기시작한 시간 + 먹는시간
  	}
  	return ret;
  }
  
  int main() {
      ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  	cin >> C;
  	while (C--) {
  		int n = 0;	cin >> n;
  		vector<pair<int, int>> vec(n);
  		
  		for (int i = 0; i < n; ++i) cin >> vec[i].second;	// 데우는 시간
  		for (int i = 0; i < n; ++i) cin >> vec[i].second;	// 먹는 시간
  		
  		cout << solve(vec) << '\n';
  	}
  }	// 수행 시간: 32ms

  • 먹는데 소요되는 시간 순으로 내림차순 정렬한다.
  • 0번째 인덱스부터 차례대로 먹기 시작한 시간 (현재시간 + 데우는 데 걸리는 시간) + 먹는 시간을 계산해서 return 한다.

Ex 03 - 문자열 합치기 (STRJOIN, 中)

• 문자는 함정이다. 문자는 전혀 신경쓰지 않고 숫자만 신경쓰면 된다.

• 여러 번 테스트 케이스를 만들어서 손으로 풀어보자. 낮은 숫자 순으로 만들면 최소 반복이 된다는 것을 확인할 수 있다.

  • e.g. 3, 1, 3, 4, 1 의 경우 -> 1, 1, 3, 3, 4 로 정렬한다.
    1 + 1 = 2 -> 2, 3, 3, 4 (2)
    2 + 3 = 5 -> 5, 3, 4 (2+5)
    3 + 4 = 7 -> 5, 7 (2+5+7)
    5 + 7 = 12 -> 2 + 5 + 7 + 12 = 26

• 정당성 증명은 스킵한다. (교재 참고)

• 코드를 작성해보자

  #include <iostream>
  #include <queue>
  using namespace std;
  
  int main() {
      ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  
  	int C = 0;	cin >> C;
  	while (C--) {
  		int n = 0;	cin >> n;
  		priority_queue<int, vector<int>, greater<int>> pq;
  
  		for (int i = 0; i < n; ++i) {
  			int input;	cin >> input;
  			pq.push(input);
  		}
  
  		int ans = 0;
  		while (pq.size() != 1) {
  			int lhs = pq.top();	pq.pop();
  			int rhs = pq.top();	pq.pop();
  			int tmp = lhs + rhs;
  			ans += tmp;		// 값에 더해준다.
  			pq.push(tmp);	// push 하면 자동으로 크기 순으로 정렬되어 들어간다.
  		}
  		
  		cout << ans << '\n';
  	}
  }	// 수행시간: 0ms

마무리

• Greedy 알고리즘은 Bruteforce와 DP보다 훨씬 빠르고 메모리도 적게 사용해서 최적해를 구할 수 있다.
• 그러므로 적재적소에 greedy 방법을 선택할 수 있는 능력을 기르는것이 중요하다.
• Greedy 알고리즘이 최적해를 구할 수 있음을 반드시 증명해야한다. 증명 방법은 다음과 같다.
  1. Greedy 방법이 아닌 다른 방법으로 최적해를 구할 수 있다고 가정한다.
  2. 그 방법을 조금 비틀어서 (순서를 바꾸거나 등) greedy 방법으로 바꾼다.
  3. greedy 방법을 써도 해당 최적해를 구하는데 지장이 없거나 손해가 없음을 증명한다.
  4. 부분해의 최적해가 전체 답안의 최적해임을 증명한다.