[PS] 그리디 알고리즘

그리디 알고리즘

현재 상황에서 가장 좋은 것만 고르기

 

 

✨현재 상황만을 고려하고 나중에 미칠 영향에 대해서는 고려하지 않는다.

✨ 기준에 따라 좋은 것을 선택하므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 등 기준을 제시한다.

✨ 정렬 알고리즘과 짝을 이룬다. 거스름돈을 생각한다.

 

 

해법

그리디 알고리즘으로 해법을 찾았을 때, 그 해법이 정당한지 검토해야 한다.

10000, 5000, 1000, 100, 50, 10 의 거스름돈의 경우 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

 

 

 

알고리즘 유형 유추

1. 문제 유형을 파악하기 어렵다.
2. 탐욕적인 해결법이 존재한다.
3. 그래도 해결 방법을 못 찾겠다면 다이나믹 프로그래밍이나 그래프 알고리즘을 의심한다.

 

.