그리디 알고리즘(파이썬)

그리디 알고리즘

탐욕 알고리즘이라고도 하며 매 선택에서 지금 이 순간 당장 최적인 값을 선택하여 적합한 결과를 도출하는 알고리즘 입니다. 그렇기 때문에 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.

보통 지역 최적화를 통해 전역 최적화를 도달하길 기대합니다.

특징

• 각 단계에서의 최적의 해답을 찾아 나가면서 전체 문제의 최적 해답을 찾아나가는 방식.
  각 단계에서의 결정은 지금까지의 상황만을 고려하며, 이후의 상황은 고려하지 않습니다.
• 탐욕 선택 속성, 최적 부분 구조 특성을 가지는 문제들을 해결하는 데 강점이 있습니다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.
• 문제에서 요구되는 바와 같이 사용할 정당성이 있는지 분석하는 것이 중요합니다.
• 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.

정당성

1. 탐욕 선택 속성

• 지금 이 순간의 최선의 선택이 전체에서도 최선인 결과로 이어지는가?
  즉, 앞으로의 선택을 바꾸지 않아도 된다는 보장되야 합니다.

2. 최적 부분 구조

• 전체 문제의 최적해는 부분 문제의 최적해를 포함하고 있는가?
  즉, 어떤 문제의 해가 부분 문제들의 해로 구성되어 있을 수 있어야합니다.
  ex) 전체 금액의 최소 동전 수 = 일부 금액의 최적 동전 수 + 나머지 금액의 최적 동전 수

작동 방법 예시

문제는 루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들어야 합니다.

그리디 알고리즘에 따르면 위에와 같이 루트노드 5에서 가장 큰 10, 하위 트리에서 가장큰 4의 순서로 전개됩니다.

그러나 사실은 5 → 7 → 9 로 21이 최댓값으로 나옵니다.

보통 그리디 알고리즘은 최적의 해를 보장하지 못합니다. 그래서 코딩 문제의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 추론할 수 있게끔 출제됩니다. (ex. 가장 큰/작은 순서대로)

대표문제

백준 11047 동전 0 문제이다. 이 문제의 의도는
주어진 K원을 만들때 동전의 개수를 최소한으로 출력하고 싶다. 그럴려면 K원 한도내에서 제일 큰 동전을 출력해야한다.

import sys
input = sys.stdin.readline

# 그리디 알고리즘
def coin_counter(N, K, coin):
    count = 0
    
    for i in range(N-1, -1, -1):   # range는 stop값 직전까지 반복하여 0까지 반복
        count = count + K // coin[i]  # 몫이 결국 동전의 갯수
        K = K % coin[i]   # 남은 가격 만큼 재계산
    return count

# 입력단
N, K = map(int, input().split())  # N: 동전의 종류, K: 만들 가격
coin = []
for i in range(N):
    coin.append(int(input().strip()))

print(coin_counter(N, K, coin))