알고리즘 - 그리디(Greedy) 알고리즘

그리디 알고리즘

미래를 고려히지 않고 오직 현재 시점에 가장 좋은 선택 

ex) 백준 - 동전0(11047)

핵심은 최소 동전 수이다. N개의 동전 중 금액이 제일 큰 것부터 가능한 많이 사용하고 그 다음 큰 동전 사용하기를 반복하면 된다. 그러므로 가장 큰 금액부터 최대한 많이 소진하고 뒤에있는 동전은 신경쓰지 않는다.

---

특징

미래를 신경쓰지 않고 현실에만 충실한 게 최적의 해가 될 수 있을까? 항상 보장하지 못한다. 그러므로 근사 알고리즘이라고 한다.

01 탐욕스런 선택 조건(Greedy Choice Property)

현재의 선택이 미래의 선택에 영향을 주지 않는다. 예를 들어 서울-대전-부산에 가는 방법

02 최적 부분 구조 조건(Optimal Substructure)

부분의 최적 해가 모이면 전체의 최적 해가 된다. 하나의 큰 문제를 여러개의 작은 문제들로 나눌 수 있고 이 작은  문제들에 대한 최적의 해가 더해진 것이 곧 전체 문제에 최적해가된다는 조건이다.

---

전략

어떻게 정렬해야 이 2가지 조건을 만족할 수 있을까가 중요하다.

ex) 백준 회의실 배정(1931)

하나의 회의실을 사용하고 싶다는 N개의 사용 요청을 입력 받는다. 각 요청은 회의 시작 시간과 종료 시간 정보를 제공하는데 겹치지 않는 회의시간을 최대 몇 개까지 진행할 수 있는지 계산하는 문제이다.

이를 그리디하게 풀기하기 위해서는 언제 끝냐는가가 중요하다. 그러므로 종료시간을 오름차순으로 정렬하고 제일 빠른 종료시간을 가진 회의를 시작하고 그 다음 해당 종료 시간 전에 시작하는 회의는 무시하고 진행 가능한 회의들을 또 진행하면 반복한다.

---

백준 추천문제

브론즈 - 2720, 10162, 5585, 4796, 2810

실버 - 2839, 11399, 11047, 1541, 1931

골드 - 11000, 1715, 1339, 1744, 1202

 

 

 

 

본 게시글은 개발자로 취직하기 유튜브( https://www.youtube.com/watch?v=_IZuE7NIeW4&t=11s )를 보고 작성하였습니다.