그리디 알고리즘(탐욕법)
탐욕적 기법(Greedy Algorithm), 이 기법은 항상 눈앞의 가장 큰 이익만을 쫒는 방법이다. 그리디 알고리즘의 가장 큰 특징은 문제의 성질이 동일하게 보존되고, 그로 인해 같은 전략을 반복적으로 실행 할 수 있는 것이다. 그리디의 대표적인 문제는 동전문제, 도시락 문제가있다. 예로 500원, 100원, 50원, 10원의 동전을 이용하여 가장 적은 갯수의 동전을 구하는 알고리즘이 대표적인 그리디문제인데 이는 각 동전이 배수라는 성질이 보존되기에 가능한 문제이다. 만약 60원, 50원,10원의 동전으로 220원을 표현할 때 그리디알고리즘으로 풀고자 60원 3개, 10원 4개로 생각하여 7개를 사용한다면, 50원4개, 10원 2개를 사용한 6개보다 많이 쓴 것으로 틀린 답이 된다. 예제로 백준의 알..