wdh2100   7년 전

Greedy랑 Dp랑 다른가요?

koosaga   7년 전

네. 

* greedy : 다양한 선택 중 가장 좋은 전략 몇가지만 시도해보는 방법입니다. 이렇게 한다면 보통 완전 탐색보다 쉽고 빠르게 동작하겠죠. 이렇게 해서 문제를 풀면 틀리기도 하지만, 증명을 해서 맞는 그리디 알고리즘을 만들 수도 있습니다.

* exhaustive search (완전 탐색) : 모든 선택을 열거하는 방법입니다. 열거를 하면 그중 좋은 전략을 찾는 것은 쉽겠죠. 

* dp : 일반적으로, 메모리 공간을 써서 중복 계산을 줄이는 모든 방법을 통칭합니다. 완전 탐색의 "메모이제이션"이 주요한 응용 예입니다. 


dp가 완전 탐색이랑 자주 엮이기 때문에, dp와 그리디를 "정반대 방법" 이라고 여기는 사람들도 있습니다. 


또한 이 개념들은 알고리즘 입문서에서 저보다 훨씬 이해하기 쉽고 제대로 설명해놨을 개념일 가능성이 큽니다. 책이나 인터넷 자료들을 찾아보세요. 

wdh2100   7년 전

대표적인 알고리즘 입문서가 어떤게 있을까요?

댓글을 작성하려면 로그인해야 합니다.