그리디 알고리즘

그리디(Greedy) 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.

• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.

그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.

하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제가 된다고 합니다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해줍니다.

그리디 알고리즘 구현

• 코드 구현

n = 1260
count = 0

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

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

print(count)

• 실행 결과

6

그리디 알고리즘의 정당성

그리디 알고리즘을 이용했을 때, 최적의 해를 찾을 수 없을 가능성이 더 큽니다.

하지만 거스름돈 문제에서는 '가장 큰 화폐 단위부터' 돈을 거슬러주는 것처럼

탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 경우엔 매우 효과적이고 직관적입니다.

그리디 알고리즘으로 해법을 찾았을 때는 그 해법이 정당한지 검토해야 합니다.

거스름 돈 문제가 그리디 알고리즘으로 풀린 이유는 무엇일까요?

가지고 있는 동전 종류에서 큰 단위가 작은 단위의 배수 형태이어서입니다.

예를 들어, 800원을 거슬러 줘야 하는데 동전의 단위가 [500, 400, 100] 인 경우가 있습니다.

• 그리디 알고리즘은? (500원 + 100원 + 100원 + 100원) 으로 4개의 동전이 필요합니다.
• 최적의 해는? (400원 + 400원) 을 거슬러 줘서 2개의 동전이 필요합니다.

거스름 돈 문제의 해결 아이디어는 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다였고,

최적해를 구했기 때문에 이 아이디어는 정당하다고 볼 수 있습니다.

• 정리

  • 그리디 해법은 그 정당성 분석이 중요합니다.
  • 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.

• 참고 : https://velog.io/@cha-suyeon/알고리즘-그리디Greedy-알고리즘과-예제-파이썬