[TIL] 그리디 알고리즘 Greedy Algorithm

그리디 알고리즘 Greedy Algorithm 

매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자는 알고리즘 설계 기법 
항상 최적의 값을 보장하는 것이 아니라 최적의 값에 '근사한 값'을 목표로 한다 

 

예시) 경로1 이 [ 1 - 1 - 1 - 100 ] 이고 경로2 가 [ 3 - 10 - 3 - 10 ] 일 때

경로1 에서는 첫 세 단계에서 최적의 답을 선택했지만 최종 가중치는 103이고

경로2 에서는 각 단계에서의 선택이 더 나은 결과를 가져와 최종 가중치가 더 작아진다

이 때 경로1 에서의 선택이 그리디 방법론의 예시 

그리디 알고리즘 주요 속성

탐욕 선택 속성 Greedy Choice Property

각 단계에서 '최선의 선택' 을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우

즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다 

최적 부분 구조 Optimal Substructure

전체 문제의 최적해가 '부분 문제의 최적해로 구성' 될 수 있는 경우

즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서

최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것 

 

그리디 알고리즘 예제 (거스름돈)

# 거슬러 줘야 할 돈 N 원
N = int(input())

# 거스름돈 종류의 타입
coin_types = [500, 100, 50, 10]
result = 0

for coin in coin_types:
    result += N // coin 
    N %= coin

print(result)

 

• 가장 큰 화폐 단위부터 거슬러준다
• 화폐의 종류가 K 개라고 할 때, 예제 코드의 시간복잡도 O(K) 
• 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로
  작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 
  그리디 알고리즘으로 해결할 수 있다 

그리디 알고리즘이 잘 동작하는 다른 예시로는

크루스칼 알고리즘 (최소 신장 트리), 다익스트라 알고리즘 (최단 경로) 등이 있다