[탐욕법] Greedy method
1. 탐욕법 가장 직관적인 알고리즘 설계 패러다임 중 하나임 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없음. 그러나 모든 선택지를 고려해 보고 , 그중 전체 답이 가장 좋은 것을 찾는 두 방법과 다르게 각 단계마다 '지금' 당장 가장 좋은 방법만을 선택함 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않음 탐욕적 알고리즘은 많은 경우 최적해를 찾지 못하고 다음과 같은 경우에만 쓸 수 있음. 1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동젹 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용 2. 시간이나 공간적 게약으로 인해 다른 방법으..
2021.01.18