백준 - 그리디 알고리즘

https://www.acmicpc.net/step/33

그리디 알고리즘 단계

그리디 알고리즘이란 매 순간 최선의 선택을 함으로써 문제를 해결하는 알고리즘이다.

매 순간이라는 의미는, 동적 프로그램처럼 이전까지의 계산 결과를 사용하거나

분할 정복처럼 문제를 쪼갠 뒤 얻은 답을 사용하는 것과 다르다.

그냥 그 자리에서 선택지를 골라 다음 선택상황으로 이동하는 것이다.

 

그렇기 때문에 그리디 알고리즘은 어떤 선택이 최선의 선택인지만 논리적으로 결정한다면 쉽게 해결할 수 있다.

그리디 알고리즘 카테고리의 5개 문제에 대한 최선의 선택 기준은 다음과 같다.

 

https://www.acmicpc.net/problem/11047

백준 11047 - 동전 0

동전의 개수를 최소로 해야한다. 비싼 동전을 고르면 총합이 빨리 오르므로 비싼 동전의 수가 가장 많게 한다.

 

https://www.acmicpc.net/problem/1931

백준 1931- 회의실 배정

겹치지 않는 회의 일정을 최대로 선택해야 한다. 다음 회의가 시작하려면 이전 회의가 끝나야 하므로, 회의가 여러 번 끝나도록 한다. 즉 회의를 종료 시간이 이른 순으로 정렬해 그 중 가능한 회의들을 선택한다.

 

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

백준 11399 - ATM

앞 줄에 서 있을 수록 전체 대기시간에 많이 합산된다. 따라서 대기 시간을 오름차순으로 정렬해 맨 앞 사람의 대기시간이 최소가 되도록 한다.

 

https://www.acmicpc.net/problem/1541

백준 1541 - 잃어버린 괄호

식의 결과값을 최소로 만들어야 하므로, + 구간은 짧게, - 구간은 길게 만든다.

-가 짝수 개가 될 경우 +가 되므로, -가 홀수 개일 때까지 식을 괄호로 감싼다.

 

https://www.acmicpc.net/problem/13305

백준 13305 - 주유소

기름통의 크기가 무제한이므로, 가격이 싼 주유소에서 기름을 많이 담아야 한다.

이를 위해 최저가의 주유소에 도착할 때마다 현재 최저가보다 더 싸게 파는 주유소까지의 거리만큼만 기름을 충전한다.