[알고리즘] 탐욕적 기법(Greedy Algorithm)

1. 탐욕적 기법(Greedy Algorithm)이란?

탐욕적 기법, 혹은 욕심쟁이 기법이라고 불리는 이 알고리즘은 말 그대로 욕심쟁이처럼 항상 눈앞의 가장 큰 이익만을 좇는 방법이다. 대부분의 알고리즘은 큰 문제를 작은 문제로 쪼개어 해결하는 과정을 거치는데, 탐욕적 기법은 작은 문제들을 해결하는 과정에서 전체 결과를 생각하지 않고 당장 작은 문제의 최적해를 찾고 이를 모두 더하여 최종 결과를 도출하게 된다. 이러한 기법은 생각보다 잘 통하는 경우가 많지 않다. 아래 그림을 보자.

서울에서 부산까지 최단거리로 가는 방법은 서울->대전->부산의 경로로 4.5km 이지만, 이 상황에 탐욕적 기법을 적용하면 알고리즘은 각 단계에서 최적해, 즉 가장 가까이 있는 도시로 이동하여 서울->인천->대전->부산의 경로를 선택하고 이는 전체 문제의 최단거리가 아니게 된다.

 

이처럼 탐욕적 기법은 그 한계점이 명확하지만, 각각의 작은 문제들에서 전체의 결과를 신경쓰지 않고 당장의 최적해를 찾기 때문에 문제의 해결이 상당히 단순해지고 시간복잡도도 작은 편이어서 사용할 수 있는 경우에는 최고의 알고리즘이 된다. 탐욕적 기법이 적용될 수 있는 가장 알기쉬운 예시는 거스름돈 문제이다. 물건을 판매하고 거스름돈을 줄 때, 줘야 하는 동전의 개수를 최소로 사용하여야 하는 경우 아래 예시처럼 무조건 사용할 수 있는 한 가장 큰 금액의 동전을 많이 사용하는 것이 전체 문제의 해결법이 된다.

이것이 가능한 이유는 모든 동전은 보다 단위가 작은 동전 액수의 배수이기 때문이다. 따라서 큰 금액의 동전을 더 작은 동전으로 교체하면 동전 개수가 반드시 늘어난다. 예를 들어 거스름돈이 50원일 때 30원,25원,10원 단위의 동전이 있다면 30+10+10 보다 25+25 의 경우가 더 최적해가 된다.

 

2. 적용

탐욕적 알고리즘을 적용하기 위해서는 문제가 두 가지 조건을 만족해야 한다.

1. 탐욕 선택 속성(Greedy Choice Property)
2. 최적 부분 구조(Optimal Substructure)

1 번은 이전의 선택이 이후에 영향을 주지 않아야 함을 의미하고, 2 번은 부분 문제의 최적해가 전체 문제에도 그대로 적용될 수 있어야 한다는 것을 의미한다. 또한 이는 수학적 증명이 동반되어야 하지만, 일반적으로 이러한 증명을 해 내기란 쉬운 일이 아니다. 하나의 예시를 보자.

• N 개의 도시락이 있고, 전자레인지는 단 한 대만 존재하며 한 번에 하나의 도시락만 데울 수 있으며, 각 도시락은 고유의 조리시간과 먹는 시간이 정해져 있고 데운 도시락은 바로 누군가가 먹는다고 할 때, 도시락을 적절한 순서로 조리하여 모든 도시락을 다 먹는 데 걸리는 시간이 최소가 되게 하시오.

위 문제를 해결하기 위해 임의의 도시락 1, 2 를 선택하고 각각을 데우는 데 걸리는 시간을 C1, C2 이라고 하고, 먹는데 걸리는 시간은 E1, E2 라고 하자. 

• E1 >= E2 인 경우
  • 1 을 먼저 데울 경우 : C1 + C2 + max(E2, E1-C2)
  • 2 을 먼저 데울 경우 : C1 + C2 + max(E1, E2-C1) = C1 + C2 + E1
  • 위의 두 경우에서 1 을 먼저 데우는 경우에서 E2, E1-C2 중 어떤 값이 선택 되어도  E1 보다 작으므로 1을 먼저 데우는 경우가 항상 더 적은 시간이 걸린다.
• E1 <= E2 인 경우
  • 1 을 먼저 데울 경우 : C1 + C2 + max(E2, E1-C2) = C1 + C2 + E2
  • 2 을 먼저 데울 경우 : C1 + C2 + max(E1, E2-C1)
  • 마찬가지로, E1, E2-C1 두 값 모두 E2 모다 작기 때문에 항상 2을 먼저 데우는 경우가 최적의 경우의 수이다.

이러한 수학적 증명을 통해 항상 먹는 데 시간이 오래 걸리는 도시락을 먼저 데우는 것이 최적의 것임을 알 수 있다. 하지만 일반적으로 이런 증명을 찾아내기란 쉽지 않기 때문에, 탐욕적 기법은 주로 감에 의지하거나 테스트 코드를 작성하는 방식으로 이루어 지는 경우가 많다. 이 경우, 반례를 1개만 찾아도 탐욕적 기법이 적용될 수 없기 때문에 비교적 쉽게 판단할 수 있다.