[0] 그리디 알고리즘, 문제에 적용하기(Greedy Algorithm, 탐욕) - C++

그리디 알고리즘이란? 

 

현재 시점에서의 최적의 선택을 하는 알고리즘입니다. 전체 시점에서는 그게 가장 좋은 답이 아닐 수 있습니다. 매 시점마다 당장 그 시점에서의 최선의 답을 찾는 방식이기 때문입니다. 

 

아래 그림에서 거치는 노드의 숫자 합이 가장 큰 선택을 해야 한다고 합시다.

우리 입장에선 전체 노드가 보이기 때문에 당연히 왼쪽처럼 선택을 해야 숫자 합이 0+3+100 = 103이 되므로 최적의 선택이 된다는 걸 압니다. 하지만 그리디한 선택은 당시에 위치하는 노드에서 바라볼 때 가장 큰 숫자로 가는 것이므로 오른쪽 그림처럼 선택하게 됩니다. 그리디한 선택을 한 결과(0+10+8 = 18)는 실제 최적의 답(103)보다 좋지 않은 답일 수 있습니다. 즉, 그리디 알고리즘에서 모든 선택이 최적의 선택과 일치하진 않습니다.

 

그리디 알고리즘 사용 예)

- 활동 선택 문제

- 거스름돈 문제

- 최소신장트리

- 제약조건이 많은 대부분의 문제

- 다익스트라 알고리즘

- 하프만 코딩

- 크러스컬 알고리즘

 

위의 항목들은 하나씩 업로드할 때마다 링크를 댓글에 첨부하겠습니다.

 

 

 

거스름돈 문제로 보는 그리디 알고리즘

 

문제) 

 

거스름돈 동전의 개수가 가장 적게 되는 방식을 찾아야 합니다. 그러려면 큰 돈으로 먼저 채울만큼 채우고, 그 다음 큰 돈을 보고. 이런 순으로 진행해야겠죠?

 

거스름돈 문제에서도 마찬가지로, 그리디하게 고른 모든 선택이 최적의 선택과 일치하진 않습니다.

예를 들어 동전의 종류가 500엔, 400엔, 100엔 이라고 해 봅시다. 거스름돈이 만약 800엔이라면 동전 개수가 가장 적어지는 방법은 사실 400엔짜리 동전 2개를 내는 것입니다. 하지만 그리디하게 선택한다면 500엔 1개와 100엔 3개를 내는 방식이 될 겁니다.