JAVA_코딩테스트 준비_그리디 알고리즘(탐욕 알고리즘, Greedy)

탐욕 알고리즘 (Greedy)

Greedy는 직역하면 "탐욕스러운, 욕심이 많은"이라는 뜻이다. 

탐욕 알고리즘(Greedy Algorithm)은 당장 퇴적의 상황만을 채택하여 최종적인 결과를 내는 알고리즘이다. 

탐욕 알고리즘으로 문제를 해결하는 방법으로는 다음과 같이 3 단계가 있다. 

1. 선택 절차 : 현제 상태에서 최적의 해답을 선택
   
   
2. 적절성 검사 : 선택된 값이 문제의 조건을 만족하는지 검사
   
   
3. 해답 검사 : 원래 문제가 해결되었는지 검사, 미해결 시 선택 절차(1번)으로 돌아가 위의 과정을 반복

글로 쓰니까 모르겠는데? 할 수 있다.

사실 우리가 실생활에서 그리드 알고리즘은 종종 사용했다.

바로 동전 거슬러 줄때 사용한다. 

편의점에서 일하든, 마트에서 일하든 거스름돈을 줄 때 가장 적은 동전을 활용해 잔돈을 지불해야 나중에 동전이 부족하지 않다.

예를 들어서 만원으로 4320원 짜리 물건을 사서 5680원을 거슬러 줄 때 

거스름돈 이하의 화폐중에서 가장 큰 단위 - 5천원 

가장 큰 단위를 뺀 나머지 - 680원 (5천원 한장)

또 남은 거스름돈 이하의 화폐 중에서 가장 큰 단위 - 500원 

가장 큰 단위를 뺀 나머지 - 180원 (500원짜리 하나)

또또 남은 거스름돈 이하의 화폐 중에서 가장 큰 단위 - 100원 

가장 큰 단위를 뺀 나머지 - 80원 (100원짜리 하나)

또또또 남은 거스름돈 이하의 화폐 중에서 가장 큰 단위 - 50원 

가장 큰 단위를 뺀 나머지 - 30원 (50원짜리 하나)

또또또또 남은 거스름돈 이하의 화폐 중에서 가장 큰 단위 - 10원 

나머지 30원은 10원짜리 3개로 해결 

총 5천원 한장 , 500원 하나, 100원 하나, 50원 하나, 10원짜리 3개로 해결!

-> 가장 적은 짤짤이로 거스름돈에 맞추었다.

여기서 위의 3 단계를 대입하여 말하면 

선택 절차 : 가장 큰 단위의 화폐를 선택
(적은 화폐의 갯수로 조건을 충족시키기 위해) / 5천원부터 사용

적절성 검사 : 내가 선택한 화폐가 거스름돈을 넘지 않는지 검사
(5천원 2장은 거스름돈을 넘고, 한장은 안넘으니까 한장 주고 밑의 단위 화폐로 줘야 함)

해답검사 : 선택된 화폐들의 합이 거스름돈을 넘어가는지 검사하고, (5천원, 500원, 100원 ... 짤짤이 다 합해서) 넘으면 다시 처음부터 다시, 딱 맞으면 끝 -> 거스름돈을 올바르게 줫는지 검사한 것

그런데, 만약 10원짜리가 딱 하나 있어서 하나 밖에 쓸 수 없다면?

우리는 거스름돈 5680원 중 5660원으로 20원 부족하게 거슬러 주거나 

50원짜리를 하나 더 써서 5710원으로 30원 더 주어야 한다. 

-> 최적의 값으로 줄 수 없다!

이러한 상황이 발생 하기 때문에 탐욕 알고리즘을 적용하기위해서는 두 가지 조건이 따라 붙어야 최적의 값이 나온다. 

1. 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않아야 함 
   
   
2. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결방법으로 구성됨
   (마지막 10원짜리로 해결 가능한 부분인데(부분적 문제), 하나밖에 없으면 -> 해결 안됨, 그런데 여러개 있으면 10원짜리 여러개 주는거로 해결 가능 -> 부분적 문제 해결 가능)

위의 두 조건을 만족하지 않으면 탐욕 알고리즘은 최적의 답을 구하는데 적합하지 않다. 

하지만, "최적(5680원)"이 아닌 것이지, "최적에 가까운 (5660원, 5710원)"값을 구할때는 빠르게 구할 수 잇는 알고리즘이 될 수 있다. 

이러한 특성으로 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.