알고리즘 문제 유형 - 탐욕법(Greedy Algorithm)

프로그래밍/자료구조&알고리즘

O'bin 2024. 2. 19. 15:41

탐욕법(Greedy Algorithm)

매 순간 최선의 경우만 선택 -> 모든 경우 확인하지 않아 완전탐색보다 빠름

다른 경우는 고려하지 않음 -> 그리디로 풀면 반드시 틀리는 문제 존재

반례가 없는지 신중히 고민해야함

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

1449번: 수리공 항승

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나