그리디

그리디 알고리즘 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

 

그리디 알고리즘은 다른 유형과 달리 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 최단 경로 알고리즘의 경우 플로이드 워셜, 다익스트라 알고리즘과 같은 특정 알고리즘을 미리 알고 있거나 팀 노트를 통해 준비해야 풀 수 있다. 그러나 그리디 알고리즘의 유형의 문제는 매우 다양하기 때문에 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아니다. 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 한다.

 

+) 그리디는 보통 작은 값 혹은 큰 값부터 처리하는 경우가 많기 때문에 정렬 알고리즘과도 연관이 있다.

 

예제) 거스름돈

Q. 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

Sol. '가장 큰 화페 단위'부터 돈을 거슬러 준다.

n=1260
count=0

coin_type=[500,100,50,10]

for coint in coin_types:
    count+=n//coin
    n%=coin

print(count)

O(K), K = 화폐의 종류 개수

 

그리디 알고리즘의 해법을 찾을 때는 그 해법이 정당한지 검토해야 한다. 즉, 중요한 것은 그리디 알고리즘이 '최적의 해'를 찾을 수 있는지 확인하는 것이다.

거스름돈 문제의 경우 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

대부분의 그리디 알고리즘 문제는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

 

정리

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자. 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그 때는 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민해보자.