[알고리즘] 그리디

Ne5s·2022년 9월 14일

알고리즘 정리

목록 보기

4/6

그리디(탐욕법, 욕심쟁이 알고리즘)

그리디는 단순하지만 강력한 문제 해결 방법으로,
'현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.
그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠
영향에 대해서는 고려하지 않는다.

코딩테스트에서의 그리디

'사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 점에서 코테에서 만났을 때 무작정 시도해볼 수 있다.
보통 코테에서 출제되는 그리디 알고리즘은 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을요구한다.
'가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.
그래서 정렬 알고리즘과 짝을 이뤄 출제되는 편이다.
주로 코딩테스트에서의 1~2번 문제로 출제 되는 편이다(문제 중엔 난이도가 낮은 편).

그리디 vs 브루트포스(완전탐색)

처음에 이 두가지 개념이 뭐가 다른건지 헷갈렸는데,
문제가 3개 있을 때
1번 문제는 ABCDE 중에 1개를 고르는 것이고
2번 문제는 12345 중에 1개를 고르는 것이고
3번 문제는 QWERT 중에 1개를 고르는 것이라고 한다면
그리디의 경우는 각각의 문제에서 최적의 해가 생각난다면 그냥 B, 2, E 이런 식으로 고르는 것을 말하며
브루트포스의 경우에는 1번 문제에서 A를 골랐을 때 나올 수 있는 경우의 수를 다 계산해보고, B를 골랐을 때 나올 수 있는 경우의 수를 다 계산해보고.... 모든 경우의 수를 다 계산해보게 되는 점의 차이가 있었다.
그래서 결과론적으로 최적의 해를 구하고자 하면 그리디를 쓸 수 없는 것이다.
위의 예시에서 알 수 있듯이 그리디는 보게 되는 경우의 수가 적으니 브루트포스보다 빠르다.

예제1

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

문제풀이

이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로, 간단한 아이디어만 떠올릴 수 있으면 문제를 풀 수 있다. '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다.
아래는 위 문제의 python 코드이다.

예를 들어 N이 1260원이라고 해보자.
n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += (n // coin) # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin
    
print(count)

화폐의 종류만큼 반복을 수행하게 되므로 화폐의 종류가 K개일 때 이 코드의 시간복잡도는 O(K)가 된다.

그리디 알고리즘의 정당성

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.
거스름돈 문제를 그리디로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다
예를 들어 800원을 거슬러줘야 하는데, 화폐단위가 500원, 400원, 100원이라면 그리디 알고리즘으로는 4개(500원,100원3)가 나올텐데 최적의 해는 2개(400원2)가 될 것이기 때문이다.
대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다

코테에서 문제 접근방법

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 그리디 해결법이 존재하는지 고민해보자. 오랜 시간을 고민해도 해결할 수 없다면, 그때는 다이나믹 프로그래밍(DP)나 그래프 알고리즘(DFS,BFS) 등으로 시각을 돌리는 것도 한 방법이다.