[210219]그리드 알고리즘

동빈나 유튜브 강의를 보고 작성됨

그리드 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 것이다.

예시를 들자면 루트 노드에서부터 거쳐서 가는 노드 값을 최대로 만드는 길을 찾는 문제가 있다고 하자. 그리드 알고리즘은 그 다음 노드 중 가장 큰 값인 10을 고르고 다음 노드에서는 4를 고른다.

물론 여기서 최적의 해는 5 - 7 - 9를 거친는 것이다.

하지만 문제에 따라서 그리디 알고리즘이 최적의 해를 찾는 방법이 될 수 가 있다. 따라서 문제를 읽고 잘 판단해야한다.

문제는 다음과 같다.

위의 문제는 그리드 알고리즘을 푸는 것이 최적의 해를 구할 수 있는 방법이다. 그 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수 이기 때문이다. 만약 800원을 거슬러 줘야하는데 화폐단위가 500, 400, 100원라면 400원 두 개가 최적의 해로 그리드 알고리즘은 최적의 해가 아니다. 400원의 배수로 500원을 만들 수 없기 때문이다.

파이썬 코드는 다음과 같다.

n = 1260
count = 0

array = [500, 100, 50, 10]

for coin in array:
	count += n // coin
    n %= coin
  
print(count)

문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야한다.