백트랙킹(Backtracking) vs 욕심쟁이(Greedy)

백트랙킹 (Backtracking)
: 뒤에서 추적한다? 라는 의미의 이 알고리즘은 간단하게 모든 경우의 수를 확인하여 최적의 해를 찾는 방법입니다.

( 보통 재귀함수를 이용해 구현하며, N-Queens, 외판원 문제 등이 있다.)

 

  

위 질문에 확실하게 답을 줄 수 있습니다. 

하지만 일단 모든 경우의 수를 확인하는 데 걸리는 시간, 또한 재귀 호출을 이용하는 방법 등 많은 시간이 걸리는 방법입니다.





욕심쟁이, 탐욕적 (Greedy)
:  이름 그 자체에 핵심을 많이 내포하고 있는데요. 선택한 시점에서의 가장 최고인 것 처럼 보이는 것을 선택하는 방법입니다.

최적의 해는 아니지만 근접한 해와 빠른 처리 시간의 장점을 가지고 있습니다.

 
하지만 ...

[ 동전 교환 문제 ] 
1, 5, 12, 50 단위의 동전을 최소 갯수 조합으로 거스름돈을 돌려주기. ( 단위는 외국 동전이라 그럼 -_- )

거스름돈 : 15 일 경우.

그리디 알고리즘의 경우 
[ 12 :  1개  , 1   :  3개 ] 가 나오게 된다.

하지만 정답은 [ 5 : 3개 ] 

( 이렇게 그 상황에서 최선을 고르지만 그 답은 최적해가 아닐 수가 있습니다. )

 

구현과 이해는 사람마다 다를 수 있습니다.