그리디

Greedy : 탐욕스러운, 욕심사나운, 몹시 탐내는

여러 경우 중 하나를 결정해야 할 때 마다
그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적인 해답에 도달한다.
그리디라는 이름에 걸맞게 하나를 결정 할 때마다 이게 더 좋은 선택이겠지? 싶은걸 선택하면 되는 것 같다.

그리디는 지역적으로도 최적, 전역적으로도 최적일때 답을 보장한다

---

내가 푼 그리디 알고리즘 문제


1 백준 - 동전 0 / https://www.acmicpc.net/problem/11047

• 주어진 금액을 큰순부터 나누고 나눠지는 순간부터 세는 방법으로 접근 했다.

2 백준 - ATM / https://www.acmicpc.net/problem/11399

• 인출하기 위한 최소의 시간이기에 먼저 오름차순으로 정렬 시킨뒤 순서대로 더했다.

3 백준 - 주유소 / https://www.acmicpc.net/problem/13305

• 현재 도시와 다음 도시의 주유소 리터당 가격을 비교 후
  현재가 더 높다면 당장 다음 주유소에 갈만큼만 충전,
  낮다면 다음 도시까지의 거리를 기억후 다음 도시로 이동했다.
  ( 이 때, 이 도시의 리터당 가격을 현재로 유지 )

4 백준 - 주식 / https://www.acmicpc.net/problem/11501

• 미래에 주식이 오르는지 여부를 판단하기 위해 미래부터 과거로 오며 가장 높은 주식을 확인한다.
• 현재부터 미래로 가면서 미리 알고있는 가장 높은 주식이 아니라면 주식을 구입, 아니면 판매한다.

5 백준 - 회의실 배정 / https://www.acmicpc.net/problem/1931

• 회의식의 시작과 끝 시간 중 끝을 기준으로 내림차순 정렬, 끝이 같을 경우 오름차순으로 정렬한 뒤
  회의실이 배정이 된다면 회의실 갯수를 세는 방법을 사용했다.
  • 회의실을 끝나는 시간으로 정렬하는 이유는 문제를 그림으로 그려보면 알 수 있다.