[알고리즘] 그리디 알고리즘 (Greedy Algorithm, 탐욕법)

그리디 알고리즘 (Greedy Algorithm, 탐욕법)

 

현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

매순간 좋아 보이는 것만 고르며, 현재 선택이 나중에 미칠 영향을 고려하지 않고, 상황이 오면 그때 적합한 것을 선택한다.

알고리즘이 작성할 때 두 가지 조건을 만족시켜주어야 한다.

Greedy algorithm - Wikipedia

탐욕스러운 선택 조건 (Greedy Choice Property)

각 단계에서 최적의 선택을 함으로써 전체 문제의 최적 해를 얻어야 한다.

현재 단계에서의 최적 선택이 이후 단계에서도 여전히 최적 선택으로 이어져야 하고, 이를 통해 한 번의 선택이 전체 문제 해결에 유리하게 작용하도록 구성해야 한다.

 

최적 부분 구조(Optimal Substructure)

문제의 최적 해답이 그 하위 문제들의 최적 해답으로부터 구해질 수 있는 구조여야 한다.

전체 문제의 최적 해답이 부분 문제들의 최적 해답으로 구성되어야 재귀적으로 문제를 분할하여 각 부분 문제를 해결하고 조합해 전체 문제의 답을 구할 수 있다.

 

---

 

그리디 알고리즘 대표 예제, 거스름돈 문제

def min_coins(coins, amount):
    # 동전 종류를 내림차순으로 정렬
    coins.sort(reverse=True)
    
    result = []
    
    # 남은 금액
    remaining_amount = amount
    
    # 각 동전으로 채울 수 있는 만큼 채우기
    for coin in coins:
        count = remaining_amount // coin  # 현재 동전으로 채울 수 있는 최대 개수
        remaining_amount -= count * coin  # 채운 만큼 남은 금액에서 빼기
        result.append((coin, count))  # 결과에 추가
        
        # 남은 금액이 0이 되면 종료
        if remaining_amount == 0:
            break
    
    return result

# 동전 종류와 금액 설정
coins = [100, 50, 10, 1]
amount = 126

# 함수 호출
result = min_coins(coins, amount)

# 결과 출력
print("동전 종류와 개수:")
for coin, count in result:
    print(f"{coin}원: {count}개")

실행 결과

동전 종류와 개수:
100원: 1개
50원: 0개
10원: 2개
1원: 6개

 

---

 

그리디 알고리즘의 정당성 검토

탐욕법이 항상 최적의 해답을 제공하지는 않는다.

거스름돈 문제에서도 동전 다위가 100, 50, 10, 1 처럼 큰 단위가 작은 단위의 배수일 때 탐욕법이 최적의 해답을 보장한다.

문제를 접했을 때 탐욕법, 그리디 알고리즘을 떠올려보고, 정당성이 부족하다면 동적 계획법(DP)이나 그래프 알고리즘 등 다른 접근 방식을 고려해야 한다.

탐욕법의 일반적인 예시들로는

1. 거스름돈 문제: 동전 단위가 배수 관계일 경우
2. 최소 신장 트리: Kruskal's Algorithm, Prim's Algorithm
3. 다익스트라 알고리즘: 최단 경로 찾기
4. 허프만 코딩: 최적의 접두어 코드 생성

외에도 제약 조건이 많은 문제에서도 탐욕법으로 풀리는 경우가 있다.

앞서 알아본 탐욕스러운 선택 조건, 최적 부분 구조 만족를 만족하는지 검토해보고 적용 되지 않는다면 다른 조건을 사용해 접근해야한다.