[알고리즘 설명][Python] 그리디 알고리즘(greedy)

이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.

혹시나 모르는 부분이 있으면 댓글로 질문해주세요.

 

한 줄 요약 : 현재 단계에서 최적해를 구하는데 과거 데이터(캐시)의 영향을 받지 않으면 그리디 알고리즘, 과거 데이터(캐시)의 영향을 받으면 다이나믹 프로그래밍 알고리즘을 사용하면 됩니다.

추가로 그리디 알고리즘의 점화식은 dp[i] = dp[i-1] + alpha이며 이것은 벨만 방정식에서 선택지가 1개 뿐인 경우와 동일합니다.

따라서 그리디 알고리즘은 알고 보니 다이나믹 프로그래밍의 특수해이며 결국 그리디 알고리즘은 점화식이 dp[i] = dp[i-1] + alpha인 다이나믹 프로그래밍으로 변환됩니다.

 

개념은 쉬우나 적용하기가 상당히 어려운 3대 알고리즘 패러다임이 존재합니다.

- 다이나믹 프로그래밍

- 그리디 알고리즘

- 분할 정복 알고리즘

이번에는 그리디 알고리즘에 대해 간단하게 알아보겠습니다.

 

다이나믹 프로그래밍은 초기식과 점화식을 구하기가 매우 어려우나 어쨋거나 한 번 초기식과 점화식을 구해놓으면 그 다음부터 구현은 정말로 쉬워집니다.

 

하지만 그리디 알고리즘은 다이나믹 프로그래밍보다 더 간단합니다.

그리디 알고리즘이 "각 단계마다 부분 최적해를 구해서 전체 문제의 최적해를 구하는 알고리즘"이라고 되어 있지만 이건 컴퓨터 공학에서 멋있게 만든 정의입니다.

 

PS 문제를 직접 해결한 분들이라면 알겠지만 그리디 알고리즘은 "아 몰라! 그냥 지금 당장 가장 적거나 큰 것만 골라! 그러면 어떡하든 정답이 되겠지 뭐!"입니다.

 

그리디 알고리즘은 사용하는 도구가 딱 3가지 뿐입니다.

1. 정렬 -> 정렬해서 무조건 가장 큰 놈만 혹은 가장 작은 놈만 골라!

2. max(), min() -> 무조건 최대로! 무조건 최소로!

3. 우선순위 큐 -> 1등 아니면 꼴지만 골라!

이게 끝입니다.

 

그런데 왜 그리디 알고리즘이 어렵냐?

"막 골랐는데 그게 정답임? 어떻게 증명할거임?"

이게 문제입니다. 부분 최적해 모음이 전체 최적해인 것을 증명하는 것이 너무나 어렵기 때문입니다.

 

그나마 그리디 알고리즘을 적용할려면

1. 배열 혹은 리스트를 정렬할 수 있는가?

2. 내가 지금 선택한 것이 나중에 번복될 일이 없는가?

3. 큰 선택지 하나가 나머지 작은 선택지들을 압도하는가?

이 조건들을 만족하면 되지만 가장 중요한 것은

4. 현재 단계에서 최적해를 선정할 때 과거 데이터(캐시) 영향을 받지 않는가?

이게 가장 중요합니다.

특히 4번 조건이 있냐 없냐에 따라 그리디 알고리즘이냐 아니면 다이나믹 프로그래밍 알고리즘이냐로 갈라지게 됩니다.

 

자, 그리디 알고리즘 감각을 한 번 익혀보도록 하겠습니다.

1센트, 5센트, 10센트, 25센트, 50센트 동전이 있다고 가정합니다.

이 때 1달러(100센트)로 1달러 이하의 물건을 1개 구매해서 잔돈으로 바꿔야 합니다.

이 때 동전 몇 개 필요할까요?

아래의 소스 코드를 구현해서 한 번 알아봅시다.

import sys

input = sys.stdin.readline

coins:list = [1, 5, 10, 25, 50]

pay:int = 100 # 1달러 = 100센트
cost:int = int(input().rstrip()) # 100센트 이하의 물건 1개를 구매합니다.

if pay >= cost :
    change:int = pay - cost
    result:int = 0
    
    reversed_coins:list = sorted(coins, reverse=True)
    
    for coin in reversed_coins :
        result += change // coin
        change %= coin
        
    print(f"1달러를 주고 {cost}센트 물건을 구매하여 총 잔돈의 동전 개수는 {result}개입니다.")
else :
    print("물건이 너무 비싸서 못 삽니다.")

여기에 36센트의 물건을 하나 구매했다고 가정합니다.

그러면 64센트의 잔돈이 필요하고 50센트 동전 1개, 10센트 동전 1개, 1센트 동전 4개로 해서 총 6개의 동전을 받게 되며 이는 최소 개수입니다.

 

그런데 제가 그리디 알고리즘을 분석하다가 놀라운 사실을 알게 되었어요.

그리디 알고리즘은 dp로 변환할 수 있다는 사실을 알게 되었습니다.

자, 아래의 소스 코드를 확인해주세요.

import sys

input = sys.stdin.readline

coins:list = [1, 5, 10, 25, 50]
coins.sort(reverse=True) # 처음부터 역순으로 합니다.

pay:int = 100 # 1달러 = 100센트
cost:int = int(input().rstrip()) # 100센트 이하의 물건 1개를 구매합니다.

if pay >= cost :
    change:int = pay - cost # 잔돈 = 100센트(1달러) - 비용
    
    dp:list = [0 for _ in range(len(coins) + 1)]
    
    # 초기식
    dp[0] = 0
    
    # 점화식
    for i in range(1, len(coins) + 1, 1) :
        dp[i] = dp[i-1] + (change // coins[i-1])
        change %= coins[i-1]
        
    # 결과
    print(f"1달러를 주고 {cost}센트 물건을 구매하여 총 잔돈의 동전 개수는 {dp[-1]}개입니다.")
else :
    print("물건이 너무 비싸서 못 삽니다.")

이렇게 해도 36센트를 입력하면 똑같이 6개로 나옵니다.

이것을 통해 그리디 알고리즘은 결국 다이나믹 프로그래밍의 특수해라는 것을 증명했습니다.

즉, 다이나믹 프로그래밍에서 아래의 점화식 형태를 만족하면 그리디 알고리즘이 성립됩니다.

$$ dp[i] = dp[i-1] + \alpha $$

그래서 그리디 알고리즘은 위의 점화식을 만족하므로 result += alpha 형식의 코드 한 줄로 정리되어 메모리 절약까지 가능합니다.

단, 다이나믹 프로그래밍 게시글에서 이미 알고 있겠지만 초기식 및 점화식 유도 및 증명하는 것이 극악의 난이도이며 그리디 알고리즘도 위 점화식을 유도 및 증명하기가 정말로 어렵기 때문에 그리디 알고리즘 문제들이 악명이 높은 것입니다.

추가로 alpha 이거 하나 구하기가 정말로 어려운 것도 한몫합니다.

 

이상 그리디 알고리즘에 대해 간단하게 알아봤습니다.