[알고리즘] 그리디 알고리즘

그리디 알고리즘

탐욕법은 가장 직관적인 알고리즘 설계 패러다임

원하는 답을 재귀호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없지만 모든 선택지 중 전체 답이 가장 좋은 것을 찾는 두 방법과는 다르다.

각 단계마다 지금 당장 가장 좋은 방법만을 선택한다.

예제 : 회의실 예약

→ 길이와 상관없이 먼저 끝나느 회의부터 선택

1. 목록 S에 남은 회의 중 가장 일찍 끝나는 회의 S(min) 을 선택한다.
2. S(min) 과 겹치는 회의를 S 에서 모두 지운다.
3. S 가 텅 빌 때까지 반복한다.

→ 집합의 크기가 n 일 때 부분 집합의 갯수는 n^2

→ 그리디 알고리즘으로 풀면 시간복잡도 O(nlogn)