[알고리즘] Greedy Algorithm 탐욕 알고리즘 / 파이썬

탐욕 알고리즘 (Greedy Algorithm)

최적 해를 구하는데 사용되는 근시안적인 방법

 

탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.

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

 

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.

 

 

탐욕 알고리즘 수행 과정

1. 해 선택

현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분 해 집합에 추가한다.

2. 실행 가능성 검사

새로운 부분 해 집합이 실행 가능한지를 확인한다.

즉, 문제의 제약 조건을 위반하지 않는지를 검사한다.

3. 해 검사

새로운 부분 해 집합이 문제의 해가 되는지를 확인한다.

아직 전체 문제의 해가 완성되지 않았다면 1.해 선택 부터 다시 시작한다.

 

 

탐욕 알고리즘 예

거스름돈 줄이기

Q. 어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정하자.

손님에게 거슬러 줘야 할 돈이 1,260원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.

 

1. 해 선택

가장 좋은 해를 선택한다.

이 문제에서는 가장 단위가 큰 동전을 거슬러 주는 것이다.

 

즉, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다.

 

2. 실행 가능성 검사

거스름돈이 손님에게 내드려야 할 액수를 초과하는지를 확인한다.

초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고, 1. 해 선택으로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가한다.

 

500원짜리 2개를 거슬러주면, 1,260원을 초과하지 않으므로 3. 해 검사로 넘어간다. 

 

3. 해 검사

거스름돈이 손님에게 내드려야 하는 액수와 일치하는지 확인한다.

액수에 모자라면 다시 해 선택으로 돌아가서 거스름돈에 추가할 동전을 고른다.

 

현재 거스름돈은 500*2 = 1,000 원이므로 1,260원과 일치하지 않는다.

액수가 모자라기 때문에 다시 1. 해 선택으로 돌아가서 그 다음 큰 동전인 100원을 고르고 과정을 반복한다.

 

 

100원짜리 2개를 거슬러주면, 1,260원을 초과하지 않으므로 3. 해 검사로 넘어간다.

현재 거스름돈은 500 * 2 + 100 * 2 = 1,200 원이므로 1,260원과 일치하지 않는다.

액수가 모자라기 때문에 다시 1. 해 선택으로 돌아가서 그 다음 큰 동전인 50원을 고른다.

50원짜리 1개를 거슬러주면, 1,260원을 초과하지 않으므로 3. 해 검사로 넘어간다.

현재 거스름돈은 500 * 2 + 100 * 2 + 50 * 1 = 1,250 원이므로 1,260원과 일치하지 않는다.

액수가 모자라기 때문에 다시 1. 해 선택으로 돌아가서 그 다음 큰 동전인 10원을 고른다.

10원짜리 1개를 거슬러주면,  1,260원을 초과하지 않으므로 3. 해 검사로 넘어간다.

현재 거스름돈은 500 * 2 + 100 * 2 + 50 * 1 + 10 * 1 = 1,260 원이므로 1,260원과 일치한다.

 

즉, 손님에게 거슬러 줘야 할 돈이 1,260원일 때 거슬러줘야 할 동전의 최소 개수는 2개 + 2개 + 1개 + 1개 = 6개 이다.

 

 

※ 탐욕 알고리즘 접근의 경우, 해답을 찾아내지 못하는 경우도 있음.

 

 

참조

https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do

SW Expert Academy