탐욕법(Greedy Algorithm)
매 순간 최선의 경우만 선택 -> 모든 경우 확인하지 않아 완전탐색보다 빠름
다른 경우는 고려하지 않음 -> 그리디로 풀면 반드시 틀리는 문제 존재
반례가 없는지 신중히 고민해야함
< 백준 예제 문제 >
https://www.acmicpc.net/problem/11047
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
https://www.acmicpc.net/problem/1449
1449번: 수리공 항승
첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나
www.acmicpc.net
'프로그래밍 > 자료구조&알고리즘' 카테고리의 다른 글
| 검색 알고리즘_해시법 (0) | 2024.04.10 |
|---|---|
| 검색 알고리즘_이진 검색(binary search) (0) | 2024.03.20 |
| 검색 알고리즘_선형 검색(linear search), 보초법 (0) | 2024.03.20 |
| 알고리즘 문제 유형 - 완전탐색(permutation, combination) (0) | 2024.02.14 |
| 자료구조(배열, 연결리스트, 스택, 큐, 맵, 집합) (1) | 2024.02.11 |