그리디란?
그리디 알고리즘은 현재의 최적 해를 구하는 알고리즘이다. 즉, 미래를 생각하지 않고 현재에서의 최선의 값을 구하는 방식인데 이는 전체 구조에서의 최적 해가 될 수 없기에 근사 알고리즘이라고도 한다.
최적해를 위한 조건
근사 알고리즘인데 어떻게 정확한 값을 요구하는 코테에서 사용할 수 있을까? 해당 문제로 인해 코테에서 그리디를 사용하기 위해서는 2가지의 조건이 필요하다.
- 현재의 결정이 미래에 영향을 주지 안는다.
- 부분의 최적 해가 전체의 최적 해가 된다.
1 조건에 따라 서울에서 대전까지의 최적 경로 결정은 미래의 대전에서 부산까지의 최적해 결정에 영향을 주지 않는다.
2 조건에 따라 서울 대전의 최적해 및 대전 부산의 최적해는 결국 전체의 최적 해가 된다.
그리디 전략
그리디의 전략은 정렬이다. 그리디로 문제를 풀고싶으면 어떻게 정렬해야 미래에 영향을 주지 않고 최적해를 구할수 있을지 생각을 많이 해야한다.
그리디 예제 문제
https://www.acmicpc.net/problem/2720
2720번: 세탁소 사장 동혁
각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.
www.acmicpc.net
https://www.acmicpc.net/problem/10162
10162번: 전자레인지
3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은
www.acmicpc.net
https://www.acmicpc.net/problem/5585
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
https://www.acmicpc.net/problem/4796
4796번: 캠핑
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다.
www.acmicpc.net
https://www.acmicpc.net/problem/2810
2810번: 컵홀더
첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다.
www.acmicpc.net