[알고리즘] 그리디 알고리즘 알기

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미

그리디 해법은 정당성 분석이 중요하다.

- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

매 상황에서 가장 큰 값만 고르는 것이다.

일반적인 상황에서는 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

(그 순간만 판단하기 때문에)

그리디 알고리즘을 설명하기 위해 자주 등장하는 예시 문제라고 한다.

가장 큰 단위 화폐부터 돈을 거슬러 주면 된다.

1260원을 거슬러 줘야한다고 할 때

500원부터 거슬러주면, 500 x 2 = 1000,

100원 => 100 x 2 = 200,

50원 => 50 x 1 = 50,

10원 => 10 x 1 = 10

이런 식으로

그럼 이렇게 큰 화폐 단위부터 거슬러 주는게 왜 최적의 해를 보장할까?

정당성을 항상 분석했다.

"큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올수 없다. "

라는 이유가 이 문제 해결방식에 대한 정당성 이었다.

change = 1260
count = 0

coins = [500, 100, 50, 10]

for coin in coins:
    count += change // coin
    change %= coin

print(count)

count는 몇 개의 동전을 거슬러 줄 건지에 대한 변수이다.

거스름돈을 가장 큰 단위 동전 부터 나눈 몫이 그 동전의 개수가 된다.

그리고 남은 거스름돈을 계산해야 하므로 거스름돈에서 coin을 나눈 나머지를 다시 계산해준다.

항상 생각을 해야한다. 어떻게 최적의 해를 구할 것인지

왜, 이렇게 하면 최적의 해가 나오는 것인지

그리고 반례를 항상 찾으려고 고민하고,

정당성을 유추하는 방식 또한 연습을 해야함을 느꼈다.