코딩테스트 - 탐욕법(greedy)

그리드 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 가장 좋은 것(현재 고를 수 있는 선택 중에서 가장 최적인 것)을 골라 최종 해답에 도달하는 것을 의미한다. 즉, 현재의 선택이 나중 선택에 미칠 영향을 고려하지 않는 것이다. 따라서, 일반적인 상황에서 그리드 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
하지만 코딩테스트에서는 대부분의 탐욕법 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 문제가 풀리도록 출제가 된다고 한다. 그렇기에 문제에서 가장 큰 혹은 가장 작은 순서대로와 같은 기준을 제시한다.

1. 예제 : 거스름돈
   거스름돈을 500, 100, 50, 10원짜리 동전으로 거슬러 줄 때, 가능한 최소 동전의 갯수를 구하는 문제이다. 이때 각 동전의 갯수는 무한히 존재한다고 가정한다.

n = int(input("거스름돈을 입력사이오 : "))

coins = [500, 100, 50, 10]
answer = 0

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

print(f"동전의 최소 갯수는 {answer}개 입니다.")

• 결과

거스름돈을 입력사이오 : 1380
동전의 최소 갯수는 9개 입니다.

500원 2개, 100원 3개, 50원 1개, 10원 3개 사용하면 최소 갯수이다.

2. 그리드 알고리즘의 정당성
   그리드 알고리즘의 경우에는 대부분의 상황에서 최적의 해를 찾을 수 없을 가능성이 크다. 하지만 거스름돈 문제에서 가장 큰 화폐 단위부터 돈을 거슬러 주면 최소 갯수가 나오는 것처럼 탐욕법으로 문제에 접근했을 때 정확하고 최적의 답을 찾을 수 있다는 보장이 있다면 매우 효과적이며 직관적이다. 따라서 그리드 알고리즘으로 찾은 해법이 정당한지 반드시 검토해야 한다.
   거스름돈 문제의 경우 거슬러주는 돈의 단위가 큰 것부터 작은 것까지 모두 배수의 형태이기 때문이다. 예를 들어 1200원을 거슬러 줘야하는데 거슬러주는 돈의 단위가 [500, 400, 100]이라고 하면 그리드알고리즘으로는 4개(500원 2개, 100원 2개)이지만 실제로는 3개(400원 3개)이다. 따라서 그리드 알고리즘으로 구한 해가 최적의 해가 아니라는 것이다.