그리디(Greedy) 알고리즘 : 파이썬(Python)

 

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전.

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.

어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다.

그리디 알고리즘 - 현재 상황에서 당장 좋은것만 고르는 방법!

 

대표예제) 거스름돈 계산하기

 

거스름돈으로 500, 100, 50, 10 원을 줄수 있을때 경우의 수 구하기

손님에게 거슬러줘야 할 돈이 N원일때 거슬러줘야할 동전의 최소 개수를 구하라

(단, 거슬러줘야 할 돈은 항상 10의 배수이다)

 

가장큰 화폐부터 돈을 거슬러 주면 최소의 개수가 나온다!

 

N = 1260 일때,

동전의 리스트 = [500, 100, 50, 10] 으로 정해 놓고 for 문을 돌려 N을 나눈 몫을 더해주는 방식으로 진행!

 

n = 1260
coin_list = [500, 100, 50, 10]
count = 0

for coin in coin_list:
    count += n // coin
    n %= coin

print(count)

어떤 식으로 돌아가는 지는 for 문안에서 coin, n, count를 찍어보면 알 수 있다.

coin_list 안에서 돌아가는 for 문이기 때문에 첫번째 순서부터 coin은 500, 100, 50, 10 순으로 들어가 작동하는것을 볼 수 있다.

#1260원을 500원으로 나누었을때 몫
n : 1260
coin : 500
count : 2

#260원을 100원으로 나누었을때 몫
n : 260
coin : 100
count : 4

#60원을 50원으로 나누었을때 몫
n : 60
coin : 50
count : 5

#10원을 10원으로 나누었을때 몫
n : 10
coin : 10
count : 6

 

<몰랐던 연산자>

%= 대입 연산자 (n %= coin  은 [n을 coin으로 나눈 나머지를 n에 다시 설정해준다는 뜻이다!] )

 

https://null-0.tistory.com/21

011. 파이썬의 다양한 대입 연산자 사용 방법과 활용