탐욕법 (greedy) 이란?

Greedy란? 카테고리가 탐욕법이라고 되어있는데, 이 탐욕법에 대해서 먼저 알아보자. 탐욕법이란 DP(Dynamic Programming)과 상호보완하며 사용되는데, 이번에는 탐욕법에 대해서만 알아보자. 탐욕법이란 기본적으로 현재의 최선을 반복해서 선택하는 해결방법이다. 아래의 이미지를 한번 살펴보자 위의 트리에서 실제 가장큰수는 99이다. ,하지만 탐욕법으로 하면 가장큰수는 12 이다. 왜냐하면 탐욕법은 첫번째 분기에서 1과 9중에 큰 9를 고르고, 그다음에는 3과 12중에 12를 고르기 때문이다. 이렇듯이 탐욕법은 최선의 해결법이 되지는 않지만, 빠른 결과를 산출해 낼수있는 장점이 있다. 탐욕법의 적절한 예 탐욕법의 적절한 사용순간은 언제일까? 탐욕스러운 선택 조건(Greedy choice prop..