해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다.
알고리즘의 유형 중 그리디 유형에 대해서 알아보려고 한다.
기본적인 정의는 다음과 같다.
"현재 상황에서 지금 당장 좋은 것만 고르는 방법"
이는 여러가지 알고리즘을 사용해 해결하는 유형이 아닌 단순히 창의력, 아이디어를 요구하는 유형을 의미한다.
즉, 어떠한 문제를 만났을 때, 현재 가장 좋아보이는 방법을 선택하는 유형이라고 볼 수 있다.
HINT, 사용 상황
- 가장 큰 순서대로, 가장 작은 순서대로
- 다른 알고리즘을 생각해봐도 마땅히 연결되는 알고리즘이 없는 경우
- 보통 그리디 알고리즘은 정렬 알고리즘과 짝을 이루는 경우가 많다.
예시
문제
- 손님에게 거스름돈을 걸러줘야하는데, 500, 100, 50, 10원 단위의 동전이 있다.
이 때, 최소한의 동전을 사용해 돈을 거슬러 줘야한다. 단, 거슬러 줘야할 돈은 항상 10의 배수이다.
해결
그리디 알고리즘은 먼저 아이디어를 생각해내야 한다.
-> "가장 큰 화폐부터 거슬러 주면 거슬러 주는 동전의 수가 적을 것이다"
-> 가장 큰 순서대로
코드
n = 1260
count = 0
coins = [500, 100, 50, 10]
for coin in coins:
print("사용한 코인 : ", coin)
print("사용 개수 : ", n//coin)
count += n//coin
n %= coin
print("사용한 총 동전의 수 : ", count)
해결방법의 정당성 체크
예를들어, 가지고 있는 단위가 [500, 100, 70, 10] 단위라고 하자. 사실, 70원 단위는 없지만 가정이다.
이때 거슬러줘야하 하는 돈이 140원이라고 가정하면 위의 아이디어를 사용하지 못한다.
이유는 만약 큰 돈부터 거슬러 주면 500원은 불가능하고 100 + 10*4원이고 이는 총 5개의 동전이 사용된다.
하지만 70원을 사용하면 70*2로 총 2개의 동전을 사용하면 되는 것이다. 이는 항상 큰 동전이 작은 동전의 배수가 되기때문에 가능한 얘기이다.
"가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 정당하다."
정리
- "가장 큰 순서대로, 가장 작은 순서대로" 라는 아이디어가 떠오르거나 문제에서 이러한 내용이 나온다면 그리디 알고리즘을 의심하자.
- 다른 알고리즘이 마땅히 떠오르지 않는다면 그리디 알고리즘을 의심하자.
- "아이디어를 생각하자"
- "이 아이디어의 정당성을 체크하자"
