그리디 알고리즘
- 문제를 해결하는 단계를 쪼개어 각 단계마다 그 순간에서의 최선의 선택을 하는 알고리즘
- 미래를 생각하지 않고 당장의 최선의 선택을 하기 때문에 최적해를 찾는다는 보장이 없음
그리디 알고리즘이 통하는 문제들
최적해를 찾기 위해서는 동적 프로그래밍을 해야하지만, 불필요한 계산을 너무 많이 하게 될 수 있다는 단점이 있다. 다음은 그리디 알고리즘이 통하는 문제들의 예시이다.
활동 선택 문제
한 회의실에 여러 팀이 회의를 하려고 할 때 가장 많이 할 수 있는 회의 수를 찾아라. 회의 시간은 겹칠 수 없다.
-> 끝나는 시간 순으로 오름차순 정렬하여 이전 회의가 끝나는 시간과 다음 회의가 시작하는 시간이 같거나 다음 회의 시작 시간이 큰 경우를 찾으면 된다.
거스름돈 문제
잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 있을 때 거스름돈을 최소 동전 개수로 거슬러 주는 경우를 구하라.
-> 화폐 단위가 큰 순서부터 거슬러주도록 하면 된다. 620엔이 거스름돈일 경우 500엔 1개, 100엔 1개, 10엔 2개.
