알고리즘 - 그리디 (당장 좋은 것만 선택하는 방법)

알고리즘 - 그리디

 

알고리즘 중 하나인 '그리디(Greedy)'에 대해 설명하려 합니다. 핵심적인 개념과 문제 유형, 그리고 풀이 기법에 대해 설명하겠습니다. 도움이 되셨으면 좋겠습니다.

 

그리디 알고리즘이란

 

그리디 알고리즘은 각 상황에서 최선의 선택을 하여 결과적으로 최적해를 도출하는 방법입니다. 그리디 방식은 탐욕스럽게 선택할 때마다 가장 좋아 보이는 것을 고르는 전략을 따르므로 구현이 단순하고 직관적입니다.

여기서 탐욕스럽다는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미합니다. 그리디 알고리즘을 이용하면 매순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다. 

 

코딩 테스트에서 만나게 될 그리디 알고리즘의 문제유형은 앞으로도 다루게 될 알고리즘과 비교했을 때 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있습니다. 그리디 알고리즘 자체가 암기한다고 해서  항상 잘 풀 수 있는 문제 유형이 아닙니다. 사전 지식 없이도 풀 수 있는 문제도 있겠지만, 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 합니다. 

 

보통 코딩테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력 즉, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 다시 말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 합니다.

 

그리디 알고리즘 풀이 기법

 

풀이 기법 1: 정렬 기반 그리디 정렬을 통해 문제를 간편하게 해결할 수 있는 경우가 있습니다. 배열을 특정 순서대로 정렬한 후에, 탐욕적인 선택을 적용하여 해결할 수 있습니다.

 

풀이 기법 2: 우선순위 큐를 이용한 그리디 우선순위 큐를 사용하여 효율적으로 탐욕스럽게 선택할 수 있는 경우가 있습니다. 매 순간 최선의 해를 선택하는데 용이한 구조로, 최대-최소 값 찾기 등에 적합합니다.

 

풀이 기법 3: 동적 계획법과 그리디의 접목 동적 계획법과 그리디 알고리즘을 함께 사용하여 문제를 해결할 수 있는 경우가 있습니다. 먼저 동적 계획법으로 전체적인 최적해를 찾고, 그 후에 그리디 알고리즘을 적용하여 지역적으로 최적해를 찾습니다.

 

그리디 알고리즘 예시

 

'거스름돈' 문제는 그리디 알고리즘을 대표하는 예시 문제 입니다.

 

문제 : 거스름돈을 가장 적은 개수의 동전으로 주고자 합니다. 동전의 종류는 500원, 100원, 50원, 10원이 있으며, 동전의 개수는 무한하다고 가정합니다.

 

def change(n):
    coins = [500, 100, 50, 10]
    count = 0

    for coin in coins:
        count += n // coin
        n %= coin

    return count

print(change(1260)) # 결과: 6

 

이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제 간단히 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있습니다. 그것은 바로 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것입니다.  N원을 거슬러 줘야 할 때, 가장 먼저 500원을 거슬러 줄 수 있을 만큼 거슬러 준다. 그다음 100원, 50원, 10원 짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있습니다.

 

그리디 알고리즘의 정당성

 

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아닙니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 큽니다. 하지만 거스름돈 문제에서 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것과 같이, 탐욕적으로 문제를 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적입니다.

 

그리디 알고리즘으로 문제를 해결했을 때에는 그 해법이 정당한지 검토해야 합니다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 '가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문'입니다. 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있습니다.

 

https://economicyoplait.tistory.com/29

코딩테스트 연습 사이트(온라인 저지 사이트) 소개