[Algorithm] 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘 (Greedy Algorithm)

Greedy : 탐욕스러운

 

각 단계에서 최적의 선택을 하는 방식(=Greedy) 으로 최종 답에 도달하는 알고리즘을 말한다. 단, 항상 최적의 해를 구할 수 있는 것이 아니고 특정한 경우에만 그리디 알고리즘으로 최적의 해에 도달할 수 있다. 

 

**특정한 경우 == 최적의 해를 보장할 수 있는 경우

 

예시) 백준 11399 ATM (Python)

 

줄 선 사람들이 돈을 인출하는데 걸리는 시간의 합의 최솟값을 구해야한다. 각 사람이 소요되는 시간은 이전 사람들이 걸리는 시간 + 내가 걸리는 시간 이다. 

 

각 단계의에서 최적의 선택을 하여 최종 해에 도달 할 수 있다는 것을 보장할 수 있는가?

이 경우 입력받은 걸리는 시간들을 오름차순 정렬하여 각 단계에서 (앞사람들이 걸리는 시간 + 내가 걸리는 시간)을 순차적으로 더해준다면 최종걸리는 시간의 합이 최솟값이라는 것이 보장된다. 

 

 

Python Code

import sys

n = int(sys.stdin.readline().strip())
arr = list(map(int,sys.stdin.readline().strip().split()))

res = 0
temp = 0

arr.sort() #오름차순 정렬

for i in arr: #가장 작은 값부터 순차적으로 순회
    temp += i #temp : 내가 걸린 총 시간
    res += temp #res : 각 사람이 걸린 총 시간의 합
print(res)