저번 시간에는 Dynamic Programming의 사례를 코드로 함께 구현해봤습니다. 이번 시간에는 마지막 알고리즘 패러다임, Greedy Algorithm을 배워봅시다.
🐷 Greedy Algorithm
Greedy는 우리말로 '탐욕스럽다'는 뜻을 가지고 있습니다. 그럼 Greedy Algorithm은 '탐욕스러운 알고리즘' 정도로 해석이 가능한데요. 이게 무슨 말일까요?
Greedy Algorithm은 욕심쟁이처럼 미래를 생각하지 않고 당장 눈 앞에 보이는 최적의 선택을 하는 방식입니다. 이름 그대로 목표를 달성하기 위해 매 순간마다 탐욕적인 선택을 하는 방식이 Greedy Algorithm입니다.
Greedy Algoritm은 간단하고 빠르다는 장점이 있지만 최적의 답을 보장하지 않는다는 아주 치명적인 단점을 가지고 있습니다. 이는 모든 경우의 수를 구함으로써 최적의 답을 구할 수 있다는 확신을 가질 수 있는 Brute Force와 다른 점이죠.
예를 들어 봅시다. 등산을 와서 두 산 봉우리의 가운데 가장 낮은 부분에 서있습니다. 가장 높은 곳까지 올라가고 싶은데 어떻게 해야 할까요? Greedy Algoritm에 의하면 현재 지점에서 가장 좋아보이는 방향으로 갈 것입니다.
A 봉우리는 가장 높지만 가파른 길을 거쳐야 합니다. 그에 반해 B 봉우리는 A보다는 낮지만 길이 완만하여 가기가 쉽습니다. 따라서, 당장은 B로 가는 것이 더 좋은 선택처럼 보입니다.
그러나 B는 A보다 낮은 곳이므로 결국 B에 오르게 되면 가장 높은 곳에 올라가겠다는 목표는 좌절됩니다. 이는 미래를 보지 않고 당장의 탐욕적인 선택을 하다 보니 발생하는 일입니다. 완벽하지 않은 답을 고른 것이죠.
그럼 완벽하지 않은 답을 고를 수도 있다는 단점을 안고 있는 이 알고리즘은 언제 사용하게 될까요? 만약 Greedy Algorithm 외에 생각해볼 수 있는 다른 알고리즘의 속도가 모두 굉장히 느리다고 가정해 봅시다. 그럼 대안으로 Greedy Algorithm을 쓸 수 있습니다.
때로는 완벽한 답이 아닌, 적당한 답만으로도 만족스러울 때가 있습니다. 최적의 답이 필요 없는 경우이죠. 이 때도 Greedy Algoritm을 사용해 볼 수 있죠.
하지만 역시 가장 좋은 선택은 Greedy Algorithm을 써서 완벽한 답을 구하는 것입니다. 다행히도 Greedy Algorithm을 사용했을 때 최적의 답이 보장되는 문제도 존재합니다.
🐷 Greedy Algorithm의 필요성
그럼 Greedy Algoritm을 통해 최적의 답을 구할 수 있는 문제들을 분석해봅시다. 이를 알기 위해서는 문제에서 두 가지 조건을 찾으면 됩니다.
첫 번째는 Dynamic Programming과 마찬가지로 최적 부분 구조(Optimal Substructure) 여부입니다. 이는 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있음을 뜻합니다.
두 번째는 탐욕적 선택 속성(Greedy Choice Property)입니다. 어떤 문제를 풀기 위해 한 단계씩 선택을 하게 되는데요. 이때, 각 단계에서의 탐욕스러운 선택이 최종 답을 구하기 위한 최적의 선택이 되는 것이 바로 탐욕적 선택 속성입니다.
주어진 문제가 이 두 가지 조건을 모두 갖춘다면 Greedy Algorithm이 최적의 솔루션을 보장할 수 있습니다.
예시를 함께 볼까요? 500원 동전, 100원 동전, 50원 동전, 10원 동전이 있습니다. 이때, 최대한 적은 동전을 사용해서 돈을 거슬러줘야 합니다.
이 문제는 Greedy Algorithm을 통해 최적의 답을 구할 수 있을까요? 이를 알기 위해서는 먼저 이 문제가 최적 부분 구조 조건과 탐욕적 선택 속성 조건을 충족하는지 봐야 합니다.
1800원을 거슬러줘야 한다고 합시다. 이때, 어떤 동전을 먼저 내도 상관없습니다. 우선은 첫 동전으로 500원 동전을 거슬러 줍시다. 그럼 1300원이 남습니다. 이제 동전을 최대한 적게 사용해서 1300원을 거슬러주는 부분 문제를 풀어야 합니다.
첫 동전이 100원이었다면 어떨까요? 그럼 남은 돈 1700원에 대한 부분 문제를 해결하게 되겠죠. 마찬가지로 50원이라면 1750원, 10원이라면 1790원에 대한 부분 문제를 해결해야 합니다.
이 부분 문제들에 대한 최적의 답을 구하고 이 네 가지 경우를 비교하면 기존 문제에 대한 최적의 답을 구할 수 있습니다. 따라서, 이 문제는 최적 부분 구조를 가지고 있다고 할 수 있죠.
그럼 이 문제에 탐욕적 선택 속성도 있는지 한 번 봅시다. 이 문제를 Greedy Algorithm으로 풀면 매 단계에서 어떤 탐욕적인 선택을 할 수 있을까요? 매 순간마다 최대한 큰 동전을 고를 수 있겠죠?
예를 들어, 660원을 거슬러준다고 합시다. 처음에 선택할 수 있는 가장 큰 동전은 500원입니다. 그럼 이제 160원이 남죠? 이제 줄 수 있는 가장 큰 동전은 100원입니다. 그럼 60원이 남게 되죠. 그럼 50원을 가장 큰 동전으로 줌으로써 10원이 되며 마지막으로 10원을 가장 큰 동전으로 거슬러 주며 계산이 끝납니다.
이렇듯 매 순간마다 가능한 큰 동전을 선택하는 것이 가장 좋은 선택이라는 것을 증명할 수 있으면 해당 문제는 탐욕적 선택 속성을 가지고 있다고 말할 수 있습니다. 한 번 증명해봅시다.
500원짜리 동전은 100원짜리 동선 다섯 개와 같습니다. 이때, 100원짜리 5개를 줄 바에야 500원짜리 한 개를 주는 것이 더 좋겠죠? 마찬가지로 100원짜리 하나는 50원짜리 두 개와 같은데 이번에도 50원짜리를 두 개 줄 바에야 100원짜리 한 개를 주는 것이 더 낫습니다. 50원과 10원을 비교해도 마찬가지죠.
이런 식으로 가능한 가장 큰 동전으로 거슬러주는 것이 무조건 좋다고 확신할 수 있습니다. 그럼 이 문제에는 탐욕적 선택 속성이 있다고 할 수 있습니다.
결과적으로 두 조건을 모두 갖추고 있기 때문에 이 문제를 Greedy Algorithm으로 풀면 최적의 답이 보장됩니다.
참고로 탐욕적 선택 속성이 아닌 사례는 다음과 같습니다. 만약 500원, 100원, 50원, 10원이 아닌 100원, 70원, 10원이 있다면 어떨까요? 이는 최적 부분 구조를 가지고 있지만 탐욕적 선택 속성은 아닙니다.
만약 140원을 거슬러줘야 한다면 탐욕적으로 가장 큰 동전을 우선적으로 준다고 했을 때, 100원 1개와 10원 4개를 주게 될 것입니다. 하지만 사실 70원을 2개 주는 것이 더 효율적입니다. 따라서, 이 문제에서는 탐욕적인 선택이 결과적으로 최선의 선택이 아니기 때문에 탐욕적 속성이 없다고 하는 것입니다.
🐷 최소 동전 거슬러주기
이제 위 예시를 코드로 구현해 봅시다. 최소 동전을 거슬러주는 함수 min_coin_count를 Greedy Algorithm으로 구현해보겠습니다.
이 함수는 거스름돈 총액 change와 동전 리스트 coin_list를 파라미터로 받고 거슬러주기 위해 필요한 최소한의 동전 개수를 반환합니다.
예를 들어, 1700원을 거슬러줘야 한다면 500원 3개, 100원 2개로 총 5개의 동전을 거슬러주게 되므로 최소 동전 개수는 5개가 됩니다.
우리의 목적은 매 단계에서 가능한 큰 동전을 주는 방식으로 코드를 구현하는 것입니다.
우선, 동전 개수를 누적하여 저장할 수 있는 변수 count를 선언해야 합니다.
count = 0이제 반복문을 돌면서 count에 동전 개수를 추가할 겁니다. coin_list의 값을 차례로 보기 위해서는 불특정한 순서로 나열되어 있는 요소들을 정렬해야 합니다. 우리는 일전에 sorted 함수를 통해 리스트를 오름차순으로 정렬하는 방법을 배웠습니다.
그런데 이 문제에서는 리스트의 요소를 내림차순으로 정렬해야 합니다. 큰 수부터 작은 수 순서로 말이죠. 그 이유는 탐욕스러운 선택 속성에 의해 큰 동전부터 사용해야 하기 때문입니다.
sorted(coin_list, reverse=True)이 정렬된 리스트의 요소가 하나씩 반복문을 돌며 count의 수를 증가시킬 겁니다.
반복문에서 가장 먼저 해야 할 일은 현재 동전으로 몇 개를 거슬러 줄 수 있는지를 확인하는 것입니다. 이는 총액 change를 현재 coin으로 나누었을 때의 몫으로 알 수 있죠. 그 값은 그대로 count에 넣어주면 됩니다.
count += (value // coin)그 다음 나머지 연산을 통해 잔액을 계산해야 하죠. 잔액은 새로운 value값으로 갱신되고 반복문이 리스트를 마지막까지 도는 동안 coin에 의해 나눠진 후 count 수를 증가시킵니다.
value %= coin이제 전체 코드와 예시를 봅시다.
def min_coin_count(value, coin_list):
count = 0
for coin in sorted(coin_list, reverse=True):
count += (value // coin)
value %= coin
return countdefault_coin_list = [100, 500, 10, 50]
print(min_coin_count(1700, default_coin_list))5Greedy Algorithm 첫 시간, 어떠셨나요? 매 순간 탐욕스러운 선택을 한다는 것이 재밌지 않았나요?
Greedy Algorithm은 매우 흔히 사용되는 알고리즘이지만 다른 알고리즘보다는 이해하기도 쉽고 구현하기도 쉬운 것 같습니다.
다음 시간에는 Greedy Algorithm의 더 다양한 사례를 만나보도록 합시다.
* 이 강의는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.