📌 강의 바로가기
개념과 코드, 이미지는 해당 책과 강의를 참고하였습니다.
그리디 알고리즘
그리디(Greedy) 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.
- 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.
그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.
예시로 짧게 보겠습니다.
아래 루트 노드가 있습니다. 루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.
여기서 최적해는 무엇일까요?
아래처럼 5 -> 7 -> 9 로 거쳐가면 21이란 최댓값이 나옵니다.
하지만 그리디 알고리즘은 어떻게 갈까요? 놀랍게도 매순간 선택지 중 가장 최적의 해만 고릅니다.
루트 노드 5에서 시작하여 7, 10, 8 중 가장 큰 10을 선택하고, 4, 3 중에 4를 선택합니다.
그리디 알고리즘의 예시를 간단하게 보았는데요.
일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.
하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제가 된다고 합니다.
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해줍니다.
이제 예제로 그리디 알고리즘을 더 설명해보겠습니다.
예제: 거스름돈
<문제>
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
문제 해설
동전의 최소 개수를 구해야 하는 문제이기 때문에, 가장 큰 화폐 단위부터 돈을 거슬러 주는 것입니다.
거스름 돈이 N원일 때, 500원으로 최대한 많이 거슬러주고, 순서대로 100원, 50원, 10원을 써서 거슬러주면 됩니다.
이제 N이 1,260 일 때의 예시를 확인해봅시다.
문제 풀이
[Step 1] 남은 돈: 1,260원
점원에게 1,260원이 있고 이제 손님에게 동전으로 거슬러줘야 합니다.
[Step 2] 남은 돈: 260원
500원 짜리로 거슬러 줄 수 있는 돈은 1,000원입니다. 즉, 500원 2개를 빼면 260원이 남습니다.
[Step 3] 남은 돈: 60원
100원 짜리로 거슬러 줄 수 있는 돈은 200원이었습니다. 이제 60원이 남았습니다.
[Step 4] 남은 돈: 10원
50원 짜리로 1개입니다. 이제 10원만 남았습니다.
[Step 5] 남은 돈: 0원
이제 10원 1개를 써서 거스름돈을 모두 거슬러줬습니다.
그래서 결론적으로 총 6개가 필요합니다. 코드로 구현해 보겠습니다.
코드 구현
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)실행 결과
6코드를 부면 화폐의 종류만큼 반복을 수행하게 됩니다. 화폐의 종류가 K개라고 할 때 위 코드의 시간 복잡도는 입니다.
시간 복잡도에서 거스러 주어야 할 돈 N은 찾아볼 수 없습니다.
이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있습니다.
그리디 알고리즘의 정당성
그리디 알고리즘을 이용했을 때, 최적의 해를 찾을 수 없을 가능성이 더 큽니다.
하지만 거스름돈 문제에서는 '가장 큰 화폐 단위부터' 돈을 거슬러주는 것처럼
탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 경우엔 매우 효과적이고 직관적입니다.
그리디 알고리즘으로 해법을 찾았을 때는 그 해법이 정당한지 검토해야 합니다.
거스름 돈 문제가 그리디 알고리즘으로 풀린 이유는 무엇일까요?
가지고 있는 동전 종류에서 큰 단위가 작은 단위의 배수 형태이어서입니다.
예를 들어, 800원을 거슬러 줘야 하는데 동전의 단위가 [500, 400, 100] 인 경우가 있습니다.
- 그리디 알고리즘은? (500원 + 100원 + 100원 + 100원) 으로 4개의 동전이 필요합니다.
- 최적의 해는? (400원 + 400원) 을 거슬러 줘서 2개의 동전이 필요합니다.
거스름 돈 문제의 해결 아이디어는 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다였고,
최적해를 구했기 때문에 이 아이디어는 정당하다고 볼 수 있습니다.
정리
- 그리디 해법은 그 정당성 분석이 중요합니다.
- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.
