Greedy Algorithm Python

[ Greedy Algorithm ]

그리디 알고리즘(Greedy Algorithm)은 탐욕 알고리즘이라고 한다. 탐욕이라는 말이 붙기 때문에 느낌이 좀 쌔하긴 하다. 쌔한 느낌 그대로 이 알고리즘은 지금 당장 좋은 것만 골라서 사용하는 알고리즘이다. 0부터 시작하는 A라는 그래프가 있다. 이 중 가지의 합이 가장 큰 경우를 찾아야 할 때 Optimal 처럼 0-3-100을 골라내야 한다. 하지만 Greedy는 0-10-8 처럼 당장 좋은 것만 고른다. Greedy는 0에서 시작해서 3과 10의 선택 순간에 10을 선택하고 7과 8의 선택 순간에 8을 선택함으로써 탐욕을 채운다.

 

항상 최적의 결과를 만들지 않기 때문에 그리디 알고리즘으로 문제를 풀었어도 최적의 결과인지를 확인해야 한다. 최적의 결과를 만들어 줄 수 있는 내역은 가장 큰 값이 기타 작은 값들의 배수가 되었을 경우이다. [ 500원, 100원, 50원, 10원 ] 이라는 값들을 가지고 있는 리스트일 경우를 만나면 가장 큰수가 기타 값들의 배수가 되는 것을 볼 수 있다. 이럴 경우 그리디 알고리즘을 사용할 수 있는 것이다.

 

 

 

[ 잔돈 계산하기 ]

1560원을 [ 500원, 100원, 50원, 10원 ] 동전으로 같은 값을 최적으로 만들 수 있는지를 알아보겠다. 이때 500원은 100원의 배수이고 50원의 배수이고 10원의 배수이다. 이럴경우 그리디 알고리즘을 사용해서 최적의 해를 얻을 수 있다. 이렇게 주어진 값으로 계속 나누어서 값을 구하는 형태인데 주어진 값의 가장 큰값이 나머지 값의 배수라면 그리디 알고리즘으로 해결 가능하다.

n = 1560
counted = 0 
counting = 0

array = [500, 100, 50, 10]

for coin in array:
    counted += n // coin
    counting = counting + counted
    n %= coin
    print(str(coin) +"을 " +  str(counted) + "회 사용" + "그리고 " + str(n) + "남음")
    counted = 0

print("총 횟수 : " + str(counting))

> 500을 3회 사용그리고 60남음
> 100을 0회 사용그리고 60남음
> 50을 1회 사용그리고 10남음
> 10을 1회 사용그리고 0남음
> 총 횟수 : 5

 

위 코드에서 시간 복잡도를 알아보자. 화폐 종류(500, 100, 50, 10]를 K라고 하면 시간 복잡도는 O(K)이다. 빅오표기법으로 O(n)이라는 이야기 이며 화폐 종류가 많아질 수 록 알고리즘을 처리하는 시간이 길어진다고 보면 된다. for문이 하나일 경우 시간 복잡도가 O(n)이라고 보면 편하다.