[알고리즘] 탐욕 (Greedy) 알고리즘

탐욕 알고리즘(Greedy Algorithm)이란?

말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. 

탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

탐욕 알고리즘으로 문제를 해결하는 방법

1. 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

탐욕 알고리즘을 적용하기 위해 필요한 조건

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

A에서 B를 거쳐 C까지 가는 최단 경로를 찾는다고 가정해보자. A에서 B까지 가는 경로는 3가지가 있으며 C까지도 마찬가지로 3가지 경로가 있다 A에서 C까지 가는 최단 경로는 20km + 80km이다. 이 경로는 A에서 B까지 가는 최단 경로와 B에서 C까지 가는 최단 경로로 구성된다. 즉, A에서 C까지 가는 최단 경로는 각각의 부분 문제인 1) A에서 B까지 가는 최단 경로 2) B에서 C까지 가는 최단 경로의 문제의 해결 방법의 합이다.

문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다.

 

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

 

근사 알고리즘

그리디 알고리즘은 100% 최적해를 보장해주지 않는다. 다만, 어느 정도 적합한 수준의 해답을 알려준다. 따라서, 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을 때에는 사용할 수 있다. 특히, 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많기 때문에 실용적으로 사용이 가능하다. 하지만 이게 정말로 "적당히" 괜찮은지에 대해서 알려면 정확한 증명이 수반될 수 있다. 또한, 해답을 찾아가는 과정에 있어서 그리디로 구한 값을 비교값으로 설정할 수가 있다.

 

탐욕 알고리즘 사용 예시

돈 거슬러 주기

물견 가격이 총 4040원이 나왔고 계산을 하기 위해 5000원을 내밀며 거스름돈은 동전의 개수를 최소한으로 하여 거슬러야 한다. 탐욕 알고리즘에서 동전의 개수를 헤아리는 일은 우리가 일반적으로 거스름돈으로 동전을 선택하는 방법과 동일하다. 

거스름돈 5000 - 4040 = 960원을 채우기 위해서 먼저, 500원짜리 동전 한 개를 선택한다. 그리고 100원짜리 동전 네 개를 선택하고 그다음엔 50원짜리, 10원짜리 각각 하나씩 선택한다.

탐욕 알고리즘의 문제 해결 과정에 적용시키면

1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러줄 금액을 초과하는지 검사한다. 초과하면 가장 마지막에 선택한 동전을 선택하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
3. 해답 검사 : 선택된 동전들의 합이 거슬러줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번 과정부터 다시 반복

public static int coinBack(int money) {
  int[] coin = {500, 100, 50, 10, 5, 1}; // 가지고 있는 동전
  int result = 0;   // 반환할 값
  int count = 0;    // 동전 개수

  for (int el : coin) {  // coin 배열 안에 있는 원소로 순회
    if (money > 0) {
      count = money / el;
      result += count;
      money = money - (el * count);
    }
  }
  return result;
}