Greedy 알고리즘

Greedy 알고리즘이란?

 

현재 단계에서 가장 최선이라고 생각되는 선택을 반복적으로 수행하여 문제를 해결하는 방법이다.
국소적으로 최적의 선택을 하면, 그것이 곧 전체적으로도 최적의 해가 된다는 가정하에 동작한다.
특정 문제에서 간단하면서도 빠르게 최적의 해를 구할 수 있지만, 모든 문제에서는 아니다. 
따라서 문제가 Greedy로 접근하기에 적합한지를 분석하는 것이 중요하다.

 

 

 

Greedy 알고리즘의 특징

 

1. 국소 최적화:

• 매 순간 가장 좋은 선택을 하여 최적의 해를 보장한다.
• 과거의 선택은 고려하지 않으며, 미래를 예측하지도 않는다.
• 현재의 선택이 미래의 선택에 영향을 주지 않는다.
• 미래를 예측하지 않는 점 때문에 모든 문제에서 최적의 해를 보장할 수 없다. 이유는 아래에서 설명하겠다.

2. 단계적 해결:

• 문제를 여러 단계로 나눠서 각 단계마다 최적의 선택을 반복한다.

3. 빠른 실행:

• 일반적으로 Greedy 알고리즘은 다른 기법보다 구현이 간단하고 속도도 빠르다.

 

 

Greedy 알고리즘의 예시

1. 동전 거스름돈 문제

• 최소한의 동전으로 거스름돈을 주려면 어떤 동전 조합을 선택해야 하는가?

2. 활동 선택 문제

• 주어진 시간대에 최대한 많은 활동을 수행하려면 어떤 활동을 선택해야 하는가?

3. 최소 플랫폼 문제

• 기차역에서 가장 적은 수의 플랫폼으로 모든 기차를 처리하려면 어떻게 해야 하는가?

4. 최소 조합 문제

• 특정 요소를 포함한 가장 적은 수의 집합을 선택하려면 어떻게 해야 하는가?

 

 

 

Greedy가 모든 문제에서 최적의 해를 도출할 수 없는 이유

 

동전 거스름돈 문제로 이유를 자세히 살펴보자.

 

예를 들어 1750원을 최소의 동전으로 거슬러 주어야한다고 가정해보자.

 

이때 금액이 큰 500원 동전부터 거슬러 주고 그 동전으로 더이상 거슬러 줄 수 없다면, 그 다음 금액이 큰 100원 동전으로 거슬러 주는 단계를 반복한다면  최소의 동전으로 거슬러 줄 수 있을 것이다.

 

앞서 말한 과정을 거치면 500원 동전 3개, 100원 동전 2개, 10원 동전 5개로 총 10개의 동전으로 거슬러 줄 수 있다.

 

---

 

그럼 똑같이 동전을 거슬러 줄텐데 동전은 10원, 7원, 1원이 있다고 가정하고 이번에는 14원을 거슬러 줄것이다.

 

앞의 단계를 거친다면 10원 1개, 1원 4개로 총 5개의 동전으로 거슬러줄 수 있다.

그럼 이것이 최적의 해인가?

 

결과적으로 그렇지 않다. 최적의 해는 7원 짜리 동전 2개로 14원을 거슬러줄 수 있고 최적의 해는 총 2개의 동전이 된다.

 

현재 최적의 해를 선택하는 방법으로, 10원 동전을 우선적으로 선택하는 Greedy 알고리즘으로 문제를 접근하여서 7원으로 계산을 해보지 못한 것이다.

 

이렇게 현재의 최적의 해가 곧, 문제 전체의 최적의 해는 아닐 수 있다.

그래서 유사한 문제 해결 흐름이더라도 Greedy 알고리즘을 적용 시킬 수 있는 상황인지 아닌지를 잘 판별해야한다.

 

Greedy로 접근할지 여부를 판단하는 기준에 약간의 Tip은 문제에서 주어진 n값을 확인하는 것이다.

예를 들어 Back-Tracking 으로 접근해야하는 경우는 모든 경우의 수를 다 해봐야하기 때문에 비교적 n값이 작다.

하지만 Greedy로 접근해야할 경우는 루프를 한 번만 도는 경우가 많기 때문에 비교적 n값이 아주 큰 값이 나올 수 있다.