(이코테 w/ Python) 그리디 알고리즘 1
그리디 알고리즘이란?
그리디 알고리즘 (a.k.a 탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
그리디 알고리즘 문제는 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
그리디 해법은 정당성 분석이 중요하다. 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야하기 때문이다.
예를 들어, 루트 노드부터 시작하여 거쳐가는 노드 값의 합을 최대로 만들어보자.
최적의 해는 무엇일까?
루트 노드부터
5 → 10 → 4 (5+10+4) = 19
5 → 7 → 9 = 21
5 루트 노드부터 7 → 9로 가는 것이 최적의 해이다.
그렇다면 더 편한 방법으로
단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까?
매 선택 시 큰 값만 고르게 된다면 5, 10, 4를 선택하게 된다.
이는 최적의 해인 21보다 작은 19 값이 나온다.
그리디 알고리즘은 이처럼 매 상황에서 가장 큰 값만 고르는 방식과 같다.
이를 토대로 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
하지만 코딩 테스트에서의 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.
문제 1. 거스름 돈
문제 해결 아이디어
최적의 해를 빠르게 구하기 위해서 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.
N원을 거슬러 줘야 할 때 가장 먼저 500원을 거슬러 줄 수 있을 만큼 거슬러 준다.
이후 100원, 50원, 10원을 차례대로 거슬러 준다.
N= 1,260일 때
500원 두개를 거슬러 준다. (가장 큰 화폐 단위 최대로 거슬러 준다)
그 다음 100원 2개를 거슬러 주고
차례대로 50원 한 개, 10원 한 개를 거슬러 준다
그리하여 총 6개의 동전을 사용하게 된다.
정당성 분석
왜 가장 큰 화폐 단위로 거슬러 주는 것이 최적의 해를 보장할까?
가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이기 때문이다.
작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
만약 800원을 거슬러 줄 때 화폐 단위가 500원, 400원, 100원 이라면,
그리디 알고리즘에 의하면 500원 1개 100원 3개가 최적의 해이다.
하지만, 사실 400원 2개가 최적의 해 임을 알 수 있다.
다시 말해, 큰 단위가 작은 단위의 배수가 아니라면 이와 같은 알고리즘을 이용해서 최적의 해를 보장할 수 없는 것이다.
위 예시에서 500원이 400원의 배수가 아니기에 문제가 발생하는 것이다.
파이썬 코드 답안 예시
화폐를 리스트(array=[])에 담아준다
count += n//coin: 각 동전을 확인하면서 count(결과 값)에 n을 coin으로 나눈 몫을 담는다.
즉, 현재 남아있는 돈을 현재의 동전으로 최대한 많이 거슬러 줄 수 있도록 하는 것이다.
거스름 돈의 개수를 더해주는 것이다.
이후에 남은 돈은 coin보다 (해당 화폐 단위보다) 더 작아져야 하기 때문에
n %= coin: n을 코인으로 나눈 나머지 값이 될 수 있도록 한다.
다시 말해, n이 1260원 일 때, 500원으로 거슬러주게 되면
2번 만큼 거슬러줄 수 있게 되고 (n//coin)
거슬러준 다음에 260원이 남게 된다 (n%=coin)
260원을 100원으로 2번 나누어 주면 (n//coin)
60이 남게 된다.
이러한 과정을 반복해서 몇 개의 동전으로 거슬러줄 수 있는지 계산할 수 있다.
시간 복잡도 분석
화폐의 종류가 k라고 할 때, 소스코드의 시간 복잡도는 O(K)이다.
즉, 화폐의 종류만큼만 반복을 수행하면 답을 도출할 수 있다.
시간 복잡도는 화폐의 개수이다.
알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며 동전의 총 종류에만 영향을 받는다.