탐욕 알고리즘(Greedy Algorithm)

1. 탐욕 알고리즘(Greedy Algorithm) 이란?

 

• 선택의 순간에서 눈앞의 최적의 선택만을 따라가 최종적으로 답을 도출해내는 방법.
• 알고리즘을 푸는데에 있어서 최소한의 아이디어를 떠올릴 수 있는지를 물어보는 문제유형
• Greedy Algorithm은 매 순간마다 그 상황에서 최적의 값이라고 생각하는 것을 따라가지만 전체적으로 봤을 경우 그 값이 최적의 값이라고 할 수 없다.

 

2. 탐욕 알고리즘(Greedy Algorithm)의 문제 해결 방식

 

• 선택 절차 : 현재 상태에서 최적의 값을 선택
• 적절성 검사 : 선택한 값이 문제의 조건과 일치하는지 비교
• 해답 검사 : 문제가 해결되었는지 판단 후 해결되지 않았을 경우 위의 과정을 반복

 

 

• Greedy Algorithm은 항상 최적의 값을 찾아내는 것이 아니다.
• 그러면 위의 문제를 통해 Greedy Algorithm의 동작방식을 살펴보자. (나는 최고값을 찾아볼려한다.)
  1. 7과 13에서 13을 선택
  2. 5와 11에서 11을 선택
  3. 24라는 값이 제일 먼저 도출됨. 만약 내가 원하는 값이 24가 아닌 경우
  4. 5를 선택하여 18을 도출 해냄. 이것도 아닌 경우
  5. 7을 선택하게 되고 30과 100에서 100이 더 크므로 107이라는 값을 도출해냄.

• 이처럼 그 상황에서 최적(최고)의 값을 선택해 나가며 답을 도출해내기 때문에 계산의 속도가 매우 빠르다는 장점이 있다.

 

3. 탐욕 알고리즘(Greedy Algorithm)활용

 

• Greedy Algorithm을 적용할 수 있는 문제는
  1. Greedy choice property : 매 순간의 선택이 이후의 선택에 영향을 주지 않아야 한다.
  2. Optimal substructure : 매 순간 선택의 최적의 해가 문제 전체에 대한 최적의 해여야 한다.
• 위와 같은 두 조건이 붙는 문제는 Greedy Algorithm을 활용하기 적합하다.

 

4. 활용 예시

 

내가 지불해야 하는 금액이 3860원이다. 이를 10원, 50원, 100원, 500원 을 이용하여 값을 지불해야 한다. (사용해야 하는 동전의 수는 최소로)

 

주어진 동전은 500원, 100원, 50원, 10원이 있으며 동전의 갯수를 최소한으로 만들어야 하기 때문에 제일 먼저 해야할 일은 값이 가장 큰 동전의 갯수를 정하는 것이 중요하다.

 

1. 선택 절차 : 3860원에서 500원 동전을 몇개를 사용할 수 있는지 판단.

2. 적절성 검사 : 1번 에서 구한 동전의 갯수와 그 금액을 3860원에서 제외

3. 해답 검사 : 3860원을 다 거슬러 줬는지 판단 => 잔돈이 남았으면 500원이 아닌 다음 100원을 이용해 위의 과정 반복

 

이러한 동작을 반복하여 3860원을 '500원 7개', '100원 3개', '50원 1개', '10원 1개', 총 12개의 동전을 사용하여 거슬러 줄 수 있다.