코딩 테스트를 위한 그리디 알고리즘 정의

그리디(greedy) 알고리즘, 즉 말 그대로 탐욕법 혹은 욕심쟁이라는 알고리즘이다.

 

이 알고리즘을 사용하면 매 순간 가장 좋아보이는 결과물을 선택하고 이 선택이 나중에 미칠 요소는 고려하지 않는다.

 

매우 보편적인 알고리즘으로 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형이지만 특정 알고리즘 (예시: 정렬, 최단 경로 구하기 등)은 알고리즘의 사용방법을 정확히 알고 있어야 풀 가능성이 높다.

 

가장 좋은 결과물을 도출해내는 것을 기준으로 하는 알고리즘으로써 종류는 매우 다양하지만 기본적으로 '가장 큰 순서' 혹은 '가장 작은 순서'라는 의미를 가지고 있는 문제들이다.

 

1번 예시: 거스름돈

 

500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정하고 손님에게 거슬러 줄 동전의 개수를 구하는 법. (거스름돈은 항상 10의 배수)

 

이 문제의 포인트는 가장 큰 화폐 단위부터 돈을 거슬러 주는 것. 즉 가장 큰 단위인 500원의 나머지 값(%)을 구하고 다음의 화폐단위의 나머지 값(%)을 순차적으로 실행하여 주면 된다.

 

moneyGiven = 35120;
money = [500,100, 50, 10]
# 동전의 개수
count = 0;
while moneyGiven !=0:
    for i in money:
        count+=(int)(moneyGiven/i)
        moneyGiven%=i        
    
print(count)

 

그리디 알고리즘으로 문제의 해법을 찾았을 때는 이 해법이 정당한지 확인해야 한다.

 

거스름돈은 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다. 따라서 500원의 큰 단위 화폐를 먼저 거슬러 주는 것의 아이디어는 정당하다고 볼 수 있다.

 

이런 예시처럼 대부분의 그리디 알고리즘은 문제풀이의 해답이 정당한지 미리 생각하고 검토해야 답을 도출할 수 있다.

 

코딩 테스트의 문제를 풀다가 문제 유형을 파악하기 어렵다면 일단 그리디 알고리즘인지 의심해보고 그리디 해결법이 존재하는지 고민해보자. 고민해도 파악이 안된다면 나중에 배울 다이나믹 프로그래밍, 그래프 알고리즘 등으로 문제를 해결한다.