Greedy 알고리즘

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다.

 

그리디 알고리즘의 대표적 예제는 거스름 돈 문제입니다.

우리가 흔히 거스름 돈을 줄 때 가장 적은 양의 화폐를 주는 것이 제일 편합니다. 예를들어 560원을 걸러주어야 할 때 10원 짜리 56개를 주는 것 보다 500원 짜리 1개, 50원짜리 1개, 10원 짜리 1개를 주는 것이 총 3개로 더 편합니다. 따라서 이런 경우 '무조건 더 큰 화폐단위부터 거슬러 준다'는 알고리즘만 지키면 최적의 해를 보장 할 수 있습니다.

 

이러한 그리디 알고리즘은 기본적으로 무조건 큰 경우, 무조건 작은 경우, 무조건 긴 경우, 무조건 짧은 경우대로 등 극단적으로 문제에 접근한다는 점에서 정렬(Sort)기법이 함께 사용됩니다. 그 대표적인 예시가 크루스칼(Kruskal) Algorithm 으로 모든 간선을 정렬한 이후에 가장 짧은 간선부터 연결하는 최소 비용 신장 트리 알고리즘이다.

 

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 위의 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다.

그리디 알고리즘을 한마디로 설명한다면 그 유명한 마시멜로 실험에 비유할 수 있겠다. 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는 것이다. 하지만 이 방법을 사용하는 것은 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못한다.

 

 

#include <iostream>

using namespace std;

int main(void)
{
	int n, result = 0;
	cin >> n;
	result += n / 500;
	n %= 500;
	result += n / 100;
	n %= 100;
	result += n / 50;
	n %= 50;
	result += n / 10;
	cout << result;

	return 0;

}

 

예제 : 회의실 예약

• 회사에 회의실이 하나 밖에 없는데, n(<=100)개의 팀이 각각 회의하고 싶은 시간을 그림 10.1과 같이 제출했다고 할때, 이 중 서로 겹치지 않는 회의들만을 골라서 진행해야 한다. 최대 몇개나 선택할 수 있을까?

무식하게 풀 수 있을까?

• 이 문제를 무식하게 푸는 방법은 모든 부분 집합을 하나하나 만들어 보며 그중 회의들이 겹치지 않는 답들을 걸러내고 그중 가장 큰 부분 집합을 찾아낸다.
• 그러나 집합의 크기가 n일 때 부분 집합의 수는 2^n이기 때문에 n이 30만 되어도 시간 안에 문제를 풀기는 힘들다.
•  

탐욕적 알고리즘의 구상

• 이 문제를 해결하는 탐욕적인 방법은 길이와 상관 없이 가장 먼저 끝나는 회의부터 선택하는 것이다. 
  
  1. 목록 S에 남은 회의 중 가장 일찍 끝나는 회의 S(min)을 선택한다.
  2. S(min)과 겹치는 회의를 S에서 모두 지운다.
  3. S가 텅 빌 때까지 반복한다.

정당성의 증명 1 : 탐욕적 선택 속성

• 탐욕적 알고리즘의 정당성 증명은 많은 경우 일정한 패턴을 가진다.
• 우리가 처음으로 증명해야할 속성은 동적 계획 법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것이다. -> 탐욕적 선택속성(greed choice property)
• 앞서 제한 한 알고리즘의 경우, 탐욕적 선택 속성이 성립한다는 말은 다음 조건이 성립한다는 의미이다.

가장 종료 시간이 빠른 회의 S(min)를 포함하는 최적해가 만드시 존재한다.

정당성의 증명 2 : 최적 부분 구조

• 항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있을음 보여야 한다.
• 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여야한다.

구현

• 전체 시간 복잡도 O(n^2)