Greedy algoritm
그리디 알고리즘은 번역한다면 "탐욕법"이라 한다.
종종 해외 알고리즘 전공책 번역본을 본다면 탐욕법이라고 나와 있는 걸 찾아볼 수 있을 것이다.
탐욕법이라는 말 그래도 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미하는데, 그림으로 살펴보자.
최적 VS 탐욕
위 그림에 두 가지 트리가 있다.
하나는 최적의 선택을 한 트리, 또 하나는 그리디한 선택을 한 트리이다.
두 개의 트리는 같은 트리이지만 서로 다른 선택을 하고있다.
1. 최적의 선택
- 최적의 선택은 루트(맨 위 노드)노드에서 leaf(맨 아래 노드)노드까지 경로에서 노드의 합이 제일 큰 경로를 선택한 것이다.
- 그림과 같이 최적의 선택을 한 경로의 노드 합은 103이 된다.
- 그리디한 선택
- 그리디한 선택은 부모노드가 다음 자식노드들 중에서 제일 큰 노드로 경로를 선택한 방식이다.
- 루트노드의 자식노드인 3과 10중에서 큰 수인 10을 선택하고,
값이 10인 노도의 자식노드인 7과 8중에서 큰 수인 8을 선택한다. - 그림과 같이 그리디한 선택을 한 경로의 노드 합은 18이 된다.
Ex : 거스름돈 문제
슈퍼마켓에 방문한 A양은 점원인 B군에게 거스름돈을 받아야한다.
거스름 돈이 N이라고 하고, 점원은 500원, 100원, 50원, 10원 단위에 동전이 무한히 존재한다.
점원 B군이 손님인 A양에게 거슬러야 하는 돈을 최소한으로 줘야 할때, 동전의 최소 개수를 구하여라.
단, N은 항상 10의 배수이다.
위 문제를 python으로 코딩하여보자.
N = 1260 # 거스름 돈
count = 0 # 동전의 개수
# 가지고 있는 코인
array = [500, 100, 50, 10]
for coin in array :
# 제일 큰 동전부터 차례로 몫을 구하기
count += N // coin
N %= coin
print(count)
# 결과 : 6일단 거스름 돈을 1260원으로 정하고, 동전의 개수를 세줄 count변수를 0으로 초기화 하였다.
점원 B군이 가지고 있는 동전의 종류를 array에 담았다.
이때 동전은 큰 수부터 담았다. 이는 위에 그리디한 선택과 같이 제일 큰 수를 선택하기 위해 금액이 제일 큰 동전부터 내림차순으로 정렬하였다.
이제 for loop를 이용해 N에 대하여 coin으로 몫을 구하고, 이를 count에 더해주었으며 그 금액만큼 N에 빼주고 위해 나머지 연산을 해주었다.
정당성
위 문제 풀이는 그리디 알고리즘으로 풀이가 가능하다.
왜일까?
- 가지고 있는 동전에 가장 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
이와 같이 알고리즘 문제에서 그리디 알고리즘을 통해 '최적의 해'를 찾을 수 있는지 정당성을 판단해야한다.
그렇다면 정당성을 어떻게 판단할까?
위에 문제처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
정당하지 않다면?
코딩 테스트 문제를 보고, 문제 유형을 파악하기 힘들다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 있는지 고민해보자.
만약, 그리디로 해결 방법을 찾지 못했다면, 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 해결이 가능한지 살펴보자.
