Greedy(탐욕법) 알고리즘 알아보기

들어가기전에

 

 

 

 

평화로운 어느날...
운동을 열심히 하고 온 성빈이는 근무 투입 전 냉동을 폭식하고자 피엑스에 왔습니다.
그러나 사용할 수 있는 전자레인지는 1개 뿐...!
어떻게 하면 최단시간안에 조리시간이 서로 다른 여러개의 냉동을 조리하면서 먹을 수 있을까요?

 

해당 문제를 해결하기 위해서는 그리디 알고리즘을 사용해야합니다!

 

 

그리디 알고리즘이란?

그리디 알고리즘은 모든 수를 다 계산하는 동적계획법을 보완하기 위해 고안된 알고리즘으로,
여러 경우 중 하나를 결정해야할 때 그 순간에 최적이라고 생각하는 것을 선택하는 알고리즘입니다.
즉, 눈 앞에 있는 이익만을 좇는 알고리즘입니다.

마치 아기와 같습니다. ㅎㅎ

 

왜 그리디 알고리즘인가?

 

그렇다면 위의 상황에서 왜 그리디 알고리즘을 사용할까요?

앞서 말한 상황은 완전탐색 등의 알고리즘으로 접근할 수 있습니다. 다만, 그럴 경우
모든 경우를 확인하기 때문에 시간적 비용이 많이 발생합니다.
그러나 그리디 알고리즘을 사용할 경우 최적의 해를 뽑아내는 다른 알고리즘들에 비해 비용이 적은 경우가 많기 때문에 사용해야합니다.

 

 

어떻게 적용할 것인가?

 

그러면 해당 문제에서 선택을 한 이후에도 동일한 성질을 보존하고 있는 것을 찾아야합니다.
여기서는 먹는 시간, 데우는 시간이 주어지므로 먹는 경우가 오래 걸리는 냉동부터 데워야합니다.
데우는 시간은 항상 고정적이므로 우리가 자의적으로 단축할 수는 없습니다.
하지만 먹는 시간 같은 경우 냉동을 데우는 동안 먹고, 다 데우고 냉동을 먹는 시간도 고려해야하기 때문에 시간을 조절할 수 있습니다.
즉, 마지막에 데운 음식이 먹는데 가장 오래걸리는 음식이라면 시간은 지연될 수 밖에 없습니다. 그러기에 먹는데 오래걸리는 음식을 먼저 먹어야합니다.

 

 

이런 경우에는?

 

그렇다면 눈 앞에 이익만 좇는 그리디 알고리즘은 항상 통할까요?
오히려 그리디 알고리즘이 성립할 수 있는 상황은 별로 없습니다.
예시를 들어보면 다음과 같습니다.

 

 

현재 A 점에 있고 최적의 해인 M을 찾고 싶지만 그리디 알고리즘을 사용하면 눈 앞에 기울기가 큰 m방향으로 가서 지역 최적해인 m을 구할 것입니다.
위의 예시처럼 그리디 알고리즘이 성립하려면 모든 선택들은 독립적이여야한다는 탐욕스러운 선택 조건과 최종해결 방법이 부분 문제에 대해서도 같은 최적 부분 구조 조건이 성립해야합니다.
따라서 모든 문제의 성질이 동일하게 보존되고 같은 전략을 반복적으로 취할 수 있어야지 그리디 알고리즘을 사용할 수 있습니다.

 

마무리

 

 

따라서 그리디 알고리즘은 눈 앞에 있는 이익만을 추구하여 완전탐색 같은 알고리즘에 비해
시간적 비용이 적다고 말할 수 있습니다. 하지만 그리디 알고리즘이 최적의 해를 구하기 위해서는 탐욕스러운 선택 조건과 최적 부분 구조 조건이 성립하는지를 먼저
확인해야합니다.