그리디

그리디 : 탐욕

- 미래를 고려하지 않고 오직 현재 시점에 가장 좋은 선택의 알고리즘

 

가장 좋은 선택 = 가장 빠르고, 저렴한, 가장 가치있는 선택

 

 

최적해가 보장되는 조건에서만 그리디 알고리즘을 사용할 수 있다. 

 

 

조건 1. 현재의 선택이 미래의 선택에 영향을 주지 않는다. 

서울 -> 대전 초이스에 따라 대전 -> 부산 초이스가 달라지는가? 했을때 달라지지 않는다.  => [조건 성립]

그렇기 때문에 서울 -> 대전만 따졌을때 가장 좋은 선택을 하고, 대전 -> 부산만 따졌을 때 가장 좋은 선택을 한다는 것이다.  =>탐욕스러운 선택 조건 그리디 초이스 프로펄티

 

조건 2. 문제의 일부분의 최적 해가 모이면 전체의 최적 해가 된다는 것이다. 

서울에서 부산까지의 최소 거리니까 서울 -> 대전의 최소 + 대전 -> 부산의 최소

=> 최적 부분 구조 조건 optimal substructure

 

조건 3. 그리디 전략

어떻게 문제를 풀어야하는가? 정렬! 어떻게 정렬해야하냐가 관건

 

어떻게 정렬해야 미래의 선택을 고려하지 않고 현재만 고려해도 최적 해를 구할 수 있는가!

---

그리디를 사용하는 이유

 

다이나믹 프로그래밍의 사촌 동생같은 존재로 dp보다도 더 속도가 빠르다는 특징이 있다. 

완전 탐색이 가장 단순 무식하게 정답을 찾는 방식이여서 보완하기 위해 다이나믹 프로그램이을 만들게 되었다

근데 다이나믹 프로그래밍도 항상 최적 해를 보장하기 위해서는 모든 경우의 수를 고려해야한다는 단점이 있었기에 느려지게 된것.