728x90
탐욕적 기법(Greedy Algorithm), 이 기법은 항상 눈앞의 가장 큰 이익만을 쫒는 방법이다.
그리디 알고리즘의 가장 큰 특징은 문제의 성질이 동일하게 보존되고, 그로 인해 같은 전략을 반복적으로 실행 할 수 있는 것이다.
그리디의 대표적인 문제는 동전문제, 도시락 문제가있다.
예로 500원, 100원, 50원, 10원의 동전을 이용하여 가장 적은 갯수의 동전을 구하는 알고리즘이 대표적인 그리디문제인데 이는 각 동전이 배수라는 성질이 보존되기에 가능한 문제이다.
만약 60원, 50원,10원의 동전으로 220원을 표현할 때 그리디알고리즘으로 풀고자 60원 3개, 10원 4개로 생각하여 7개를 사용한다면, 50원4개, 10원 2개를 사용한 6개보다 많이 쓴 것으로 틀린 답이 된다.
예제로 백준의 알고리즘 한문제 추천
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
최솟값을 구하는 문제와, 입력조건의 배수라는 성질로 그리디 알고리즘을 유추할 수 있다.
728x90
'알고리즘' 카테고리의 다른 글
| [알고리즘] 최소비용 신장 트리 (MST) (0) | 2021.09.22 |
|---|---|
| [알고리즘] 이진검색트리(BST) (0) | 2021.09.21 |
| DP(다이나믹프로그래밍) (0) | 2021.08.03 |
| 완전 탐색(Brute-force Search) (0) | 2020.09.17 |
| 알고리즘 공부 순서 / 방법 (0) | 2020.09.17 |