Algorithm 1. Greedy(그리디)
·
코딩테스트/파이썬 알고리즘
첫번째 알고리즘은 교재의 chapter3에 해당하는 그리디이다. Greedy(그리디)는 쉽게 말해서 "당장 좋은 것만 선택하는 것 == 현재 상황에서 지금 당장 좋은 것만 고르는 것" 우선 그리디는 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는데, 그렇기 때문에 최종적(전역적)으로 최적이라는 보장은 없다. 그러나 대부분 그리디로 풀 수 있는 문제들은 "가장 큰 순서대로", "가장 작은 순서대로" 이런 조건을 제공해준다. 그리디의 대표적인 문제로 [거스름돈]이 있다. 거스름돈(p 87) 🔔 문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한..