[공주는 코딩하고 싶어] 2회차. 그리디 알고리즘 (Greedy)

그리디 알고리즘

- 현재 상황에서 지금 당장 좋은 것만 선택하는 알고리즘

- 단순하지만 강력한 문제 해결 방법

- 기준에 따라 좋은 것을 선택하는 알고리즘

  ( 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족 가능하다. 따라서 정렬 알고리즘과 짝을 이뤄 출제된다.)

- 다익스트라 알고리즘도 엄밀히 말하면 그리디 알고리즘
- 모든 알고리즘 문제에 적용 가능하진 않다. (최적의 해를 못 찾을 가능성이 많다.)
- 따라서 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.

예제. 거스름돈

문제)

500원, 100원, 50원, 10원이 무한정으로 있다고 가정하자. N원의 돈을 거슬러줘야 할 때, 4종류의 동전으로 거슬러줄 때 최소 개수를 구해라.

풀이)
가장 큰 동전으로 먼저 나누고 나머지 금액을 그 다음으로 큰 동전으로 나누는 방법을 반복하면 된다.

-> 동전의 종류 수만큼 반복해야 한다. 시간 복잡도 O(n).
(거슬러줘야 하는 돈과는 무관하다.)

ex. N = 1260
500원 2개, 100원 2개, 50원 1개, 10원 1개

정당한지 검토하기.
500원, 100원, 50원, 10원
-> 큰 수가 항상 작은 수의 배수이다.
따라서 항상 최적해를 보장할 수 있다.

why???
100원으로 5개보다 500원으로 1개가 최소 수
50원으로 2개보다 100원으로 1개가 최소 수
10원으로 5개보다 50원으로 1개가 최소 수

동전의 종류가 다른 경우
500원, 400원, 100원인 경우에 800원의 거스름돈을 나눠줘야 할 때,
그리디 알고리즘을 적용하면 500원 1개, 100원 3개가 나오지만
최적해는 400원 2개이다.
즉, 이런 경우에는 그리디 알고리즘으로 최적해를 구할 수 없다.

500원, 400원, 100원
-> 500원은 400원의 배수가 아니다.

 

2021/01/09 - [백준] - 백준 11047번 <동전 0>

백준 11047번 <동전 0>

 이것이 취업을 위한 코딩 테스트다 with 파이썬 86-102p