(욕심쟁이 스쿠르지이다. 알고리즘은 아니다.)
1. 그리디란?
Greedy Algorithm 즉, 욕심쟁이 알고리즘이다. (전에 교수님께서 스크루지에 비유하셨던 게 갑자기 생각난다..)
당장 눈 앞에 보이는 최적의 상황만을 쫒는다!
라는 외침과 함께 등장한 최적의 해(결과) 구하기 알고리즘이다. 눈 앞의 당장 좋아보이는 것만 취하기 때문에, 항상 전체의 최적 해를 보장하지는 않는다. 다만, (그래도 욕심쟁이라서) 최적 해에 가까운 근사값을 빠르게 구할 수는 있다. 그래서 그리디를 근사 알고리즘이라고도 한다.
2. 그리디, 왜 쓸까?
👉 DP보다 더 빠르다.
딱 이 한마디면 충분하다. 앞서 살펴 본 DP도 놀랍도록 빠른 시간복잡도가 강점이었는데, 그리디는 더 빠르다. 어마무시하게 빠르다.
그리디 알고리즘은 여러 분야에서 사용되는데, 스케줄링/네트워크/최단경로/최소비용신장트리(MST) 등이 있다.
그렇다면, 언제 쓸까?
그리디는 최적 해를 항상 보장하는 건 아니라고 했다. 하지만 특정한 상황에서는 그리디 알고리즘이 전체의 최적 해를 보장할 수 있는데, 그 특정한 상황은 다음과 같다.
- 현재의 선택이 미래의 선택에 영향을 미치지 않는다.
→ Greedy Choice Property (탐욕스런 선택 조건)- 부분의 최적 해가 모이면 전체의 최적 해(결과)가 된다.
→ Optimal Substucture (최적 부분 구조 조건)
즉, 한 번의 선택이 다음 선택에서는 전혀 무관한 값이어야 하며, 매 순간의 최적 해가 문제에 대한 최적 해여야 한다는 것이다. 이 두 가지를 만족한다면, 그리디 알고리즘을 통한 결과값이 근사값이 아닌 최적값이 된다!
근데, 이를 위해 그리디 알고리즘은 정렬이 중요하다. 핵심이다. 현재 선택의 갈림길 앞에서 정렬된 값들 중 최소 혹은 최대만을 취할 수 있어야 하기 때문이다. 그래서 전에 다뤘던 크루스칼 알고리즘(MST)도 그리디 기법이 적용된 사례라고 볼 수 있다.
정리하자면, 그리디는
매우 빠르게 최적(혹은 최적에 근사한) 값을 구할 수 있는 알고리즘이다.
100% 최적해를 보장하지 않아도 된다면, 그냥 편하게 그리디를 쓰고
반드시 최적해를 보장해야 하는 경우라면, 위 2가지 상황인지를 체크해서 그리디를 쓰거나 이도 아니라면 DP를 쓴다..
3. 문제
DP와 그리디는 정형화 된 접근 방식이 있다기 보다는, 많이 연습하면서 감을 가져야 한다고 한다.
[브론즈]
- 세탁소 사장 동혁 (2720)
- 전자레인지 (10162)
- 거스름돈 (5585)
- 캠핑 (4796)
- 컵홀더 (2810)
[실버]
- 설탕배달 (2839)
- ATM (11399)
- 동전 0 (11047)
- 잃어버린 괄호 (1541)
- 회의실 배정 (1931)
[골드]
- 강의실 배정 (11000)
- 카드 정렬하기 (1715)
- 단어 수확 (1399)
- 수 묶기 (1744)
- 보석 도둑 (1202)
( 문제 추천 출처 : https://www.youtube.com/watch?v=_IZuE7NIeW4 )
그리디를 한 번 뿌셔 보겠다..! (하나씩 풀어서 정리해 보겠다.)
