[알고리즘] 오늘만 사는 놈에게 죽는다, 그리디 Greedy
1. 개요
대망의 알고리즘 포스팅의 그 장대한 서막을 알리며 가장 먼저 알아볼 알고리즘은 그리디 Greedy 알고리즘이다.
자주 언급되는 여러가지 알고리즘들이 있지만 그 중에서도 첫 번째로 그리디를 선택한 이유는 솔루션에 대한 접근 방식이 아주 단순하기 때문이다.
우리말로 탐욕법이라고도 하는 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
지금 당장 좋은 것만 고르는 알고리즘이라니 정말 욕심 가득한 생각이 따로 없다. 실제로 욕심쟁이 알고리즘이라고도 불린다고 한다. 눈앞의 달콤한 이익에 취한다니 철학도로서 도저히 용납할 수 없다. 아니면 영화 '아저씨(2010)'처럼 "내일만 사는 놈은, 오늘만 사는 놈한테 죽는다", 뭐 그런건가.
아무튼 이번 포스팅에서는 욕심쟁이 그리디 알고리즘에 대해서 알아보자.
2. 사실과 오해
처음 그리디 알고리즘의 패러다임을 접했을 때는 굉장히 의문스러웠다. 당장 좋아보이는 것만 골랐는데 어떻게 최적의 해를 구할 수 있다는 걸까. 수많은 반례들이 떠오르며 그리디 알고리즘을 부정하는 싶은 지경에 이르렀다.
이는 그리디 알고리즘을 너무 일차원적으로 바라봐서 생긴 오해였다. 결론부터 이야기하면 그리디 알고리즘은 당장 좋아보이는 것을 고르는 지금의 선택이 결국엔 최적의 해를 보장한다는 확신이 있어야 가능한 알고리즘이라 할 수 있다.
그리디 알고리즘에서 흔히 거론되는 동전 문제의 예시를 살펴보자.
손님에게 거슬러줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하는 문제를 생각해보자. 거스름돈으로 500원, 100원, 50원, 10원짜리 동전이 있다면 이는 그리디 알고리즘을 적용할 수 있는 문제이다.
그리디 알고리즘을 적용할 수 있다는 말은 곧 지금 당장 좋아보이는 선택을 하더라도, 해당 문제에서는 거스름돈을 구할 때 화폐 가치가 높은 동전의 개수를 최대한으로 설정하는 솔루션이 최적의 해라는 것을 보장한다는 것이다.
그리디 알고리즘으로 정답을 구하기 위해선 정당성을 검토하는 과정이 반드시 필요하다. 이 문제에서는 화폐 가치가 높은 동전과 낮은 동전 사이에 배수 관계가 성립하기 때문에 500원을 거슬러줘야 할 일이 있으면 100원짜리 동전 5개 거슬러주는 것보다 500원짜리 동전 1개를 거슬러주는 것이 최소 개수를 줄이는데 절대적으로 유리하다.
그렇기 때문에 화폐 가치가 높은 동전의 개수를 최대한으로 설정하는 것은 곧 거스름돈으로 지급할 동전 개수를 최소한으로 줄이는 것과 동일하다.
만약 배수 관계가 성립하지 않는다면 이러한 접근 방식은 최적의 해를 보장할 수 없다.
예를 들어, 어떤 나라에서 거스름돈으로 500원, 400원, 100원짜리 동전이 있고 거슬러줘야 하는 돈이 800원인 상황을 가정해보자.
해당 상황에서는 화폐 가치가 가장 높은 500원짜리 동전을 최대한으로 사용하고 남은 금액을 100원짜리 동전으로 거슬러주는 것이 아니라 400원짜리 동전을 2개 사용하는 것이 최적의 해라는 것을 알 수 있다.
3. 알고리즘 문제에서 그리디
위와 같이 일반적인 상황에서는 그리디 알고리즘은 최적의 해를 도출할 수 없는 경우가 더 많다.
하지만 알고리즘 문제로 출제가 된다면 그리디 알고리즘으로 최적의 해를 구할 수 있다는 점을 추론할 수 있어야 풀이가 되도록 출제될 것이다. 그렇기 때문에 주어진 상황에서 직관적인 판단을 통해 최소한의 아이디어를 떠올리고 그 정당성을 검토하는 과정이 무엇보다 중요해진다.
# 참고문헌
https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2
사진출처:
https://www.yes24.com/Product/Goods/2592802
https://blog.com24everyday.com/entry/%EA%B8%B0%EB%A7%90-Greedyapproach-%EC%A0%95%EB%A6%AC