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

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

• 정의: 현재 단계에서 가장 최적이라고 생각되는 선택을 반복적으로 수행하여 최종 해답을 구하는 알고리즘이다.
• 특징: 
  1. 탐욕적 선택 속성(Greedy Choice Property)
  : 현재 단계에서의 최적 선택이 전체 문제의 최적해로 이어질 수 있어야 한다.
  2. 최적 부분 구조(Optimal Substructure)
  : 문제를 작은 부분 문제로 나눴을 때, 각 부분 문제의 최적해가 전체 문제의 최적해를 구성해야 한다.
• 동작 원리
  1. 문제를 부분 문제로 나눈다.
  2. 각 단계에서 현재 상황에서 가장 최적의 선택을 수행한다.
  3. 최적의 해가 완성될 때까지 이 과정을 반복한다.
• 장단점
  - 장점:
     - 구현이 간단하고 직관적이다.
     - 일부 문제에서는 다른 알고리즘보다 효율적이다.
  - 단점:
     - 모든 문제에서 최적해를 보장하지 않는다.
     - 문제의 성격에 따라 적합하지 않을 수 있다.

---

예제

동전 거스름돈 문제

문제: 거스름돈을 줄 때, 동전의 개수를 최소화하려면 어떻게 해야 할까?

조건: 동전의 종류가 (500원, 100원, 50원, 10원)으로 주어진다.

public class GreedyExample {
    public static void main(String[] args) {
        int[] coins = {500, 100, 50, 10}; // 동전의 종류
        int amount = 1260; // 거스름돈
        int count = 0;

        for (int coin : coins) {
            count += amount / coin; // 동전 개수 추가
            amount %= coin; // 남은 금액 계산
        }

        System.out.println("동전 개수: " + count); // 출력: 6
    }
}

 

=> 가장 큰 단위의 동전부터 사용하여 남은 금액을 줄인다.

=> 이 알고리즘은 동전의 단위가 특정 조건(큰 단위가 작은 단위의 배수)일 때 최적해를 보장한다.

---

활용 예시

1. 동전 거스름돈 문제

: 가장 큰 단위의 동전부터 사용하여 거스름돈을 계산

 

2. 회의실 배정 문제

: 가장 빨리 끝나는 회의부터 선택하여 최대한 많은 회의를 배정

 

3. 최소 신장 트리(MST)
: 크루스칼 알고리즘, 프림 알고리즘

---

탐욕 알고리즘이 적합한 문제

탐욕 알고리즘은 탐욕적 선택 속성과 최적 부분 구조를 만족하는 문제에 적합하다.

• 탐욕적 선택 속성
  : 현재 단계에서의 선택이 이후 단계의 결과에 영향을 미쳐 전체 최적해를 구성
• 최적 부분 구조
  : 부분 문제의 최적해가 전체 문제의 최적해로 연결

---

결론

탐욕 알고리즘은 문제를 단순화하고 빠르게 해결할 수 있는 강력한 도구이다.

그러나 모든 문제에서 최적해를 보장하지 않으므로, 문제의 특성을 파악하고 적합성을 판단해야 한다.