Algorithms/greedy2 알고리즘 문제 해결 전략 1권 10.탐욕법 10.1 도입 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없음. 그러나 모든 선택지를 고려해 보고 그 중 전체 답이 가장 좋은 것을 찾는 두 방법과는 달리, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택함. 탐욕법은 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않습니다. 1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만날 경우, 동적 계획법보다 수행 시간이 훨씬 빠름 2. 최적해를 찾기 너무 어렵다면 최적해 대신 적당히 괜찮은 답을 찾는 것으로 타협할 수 있음 가끔 근사해를 구하는 문제가 주어졌다 해도 탐욕적 알고리즘보다 11장에서 다루는 조합 .. 2021. 5. 14. 알고리즘 문제 해결 8장 그리디(Greedy) 현재의 상태에서 특정한 값을 기준으로 가장 좋은 것을 선택해 나가는 방법 그리디 알고리즘으로 문제를 해결하기 위해서는 어떠한 반례도 없이 항상 최적의 결과를 얻을 수 있음이 입증되어야 함 1. 현재의 상태에서 가장 좋은 것을 선택하는 것이므로 그 선택의 기준이 되는 것을 정해야 한다. 따라서 여러 가지 선택 기준 중에서 반례가 없는 기준을 찾아야 함 2. 어떤 값을 기준으로 했을 때 반례가 없다는 것이 입증이 되면 그 기준값을 기준으로 정렬하는 것이 필수임 3. 정렬이 되었다면 처음부터 차례대로 선택이 가능한 것을 모두 선택해 나가면 됨 2021. 5. 14. 이전 1 다음
