반응형 optimal substructure2 06. Greedy Algorithm(2) Greedy Technique 01. Greedy Technique suggests constructing a solution to an optimization problem through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached On each step, the choice made must be(Feasible, i.e., it has to satisfy the problem’s constraints, locally optimal, i.e., it has to be the best local choi.. 2021. 11. 18. 05. Greedy Algorithm(1) 안녕하세요. 오늘은 Greedy Algorithm. 한국어로는 탐욕적 기법이라고 하는 알고리즘을 소개할까 합니다. DP와 함께 굉장히 유명한 알고리즘인데요. 개념 자체는 이해하기 쉽습니다. 하지만 어려운 문제도 많은만큼 마스터는 어려운 파트죠. 탐욕적 기법은 말 그대로 탐욕적으로 당장 눈에 보이는 것 중에 가장 맛있어 보이는 부분(이익) 만 취하겠다는 것입니다. 물론 이런 방법이 통하지 않는 경우도 있습니다. 도시락 데우기, 파일 합치기 등은 탐욕적 기법이 통하는 유명한 문제입니다. 이런 경우는 여러 번의 선택이 모두 잘못되지 않아야 합니다. 즉, 눈 앞에 보이는 것에 대해서 취한 전략이 그 이후에도 계속 성립해야 한다는 것입니다. 많은 문제들이 딱보고 그리디라고 판단하기는 어려운데요. 쉽게 반례가 떠오.. 2021. 11. 18. 이전 1 다음 반응형
