그리디 알고리즘 문제 추천

정의

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)은 

미래에 대한 생각 없이 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘 설계 기법이다.

설명

최적의 방법은 Dynamic Programming 으로 구할 수 있지만 그 방법을 구하려고 앞으로 갔다가 뒤로 갔다가 하다보니 최종적으로 해를 구하는 시간은 느릴 수 있다.

길 찾기, 네비게이션을 예로 들면 오른쪽으로 갈지, 직진을 할지 순간 순간에 맞는 최적의 길을 갈 뿐, 그 길이 정말 가장 짧고 최종적으로 최적의 해라고는 할 수 없다. 

그래도 몇몇의 문제에서는 최적해를 빠르게 산출해낼 수 있다는 점에서 Greedy 알고리즘은 중요하다고 할 수 있다.

문제 추천

앞은 비교적 쉬운 문제이고 뒤로 갈수록 어려워지는데 좋은 문제들이라고 추천받아서 나도 정처기 시험 끝나고 바로 풀어보려고 한다. 

11047번 동전 0   https://www.acmicpc.net/problem/11047

1012번 유기농 배추 https://www.acmicpc.net/problem/1012

ATM 11399 https://www.acmicpc.net/problem/11399

로프 2217 https://www.acmicpc.net/problem/2217

2583 영역구하기 https://www.acmicpc.net/problem/2583

11000 강의실배정 https://www.acmicpc.net/problem/11000

13458 시험감독 https://www.acmicpc.net/problem/13458

4796 캠핑 https://www.acmicpc.net/problem/4796

12845 모두의마블 https://www.acmicpc.net/problem/12845

1931 회의실 배정 https://www.acmicpc.net/problem/1931

1700 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700

1969 DNA https://www.acmicpc.net/problem/1969

다른 중요한 문제 추천 

DP 문제 추천

https://won-percent.tistory.com/3

이진탐색 문제 추천

https://won-percent.tistory.com/25