욕심쟁이 알고리즘(Greedy Algorithm)

앞선 알고리즘 소개 포스트를 통해 완전 탐색을 알아보았는데, 완전 탐색(brute force)의 핵심은 큰 문제를 작은 문제로 분할하여 모든 경우를 탐색해보는 것이었으며 그 중, 작은 문제로의 분할이 가장 핵심이라고 볼 수 있다. 이는 비단 완전 탐색에 국한되는 것이 아니라 향후 다룰 동적 계획법(Dynamic Programming)이든, 지금 다룰 욕심쟁이 알고리즘이든 모든 알고리즘 문제의 가장 기본이 된다고 볼 수 있다. 완전 탐색이 모든 경우에 대해 체크한 후 최적의 해를 골라내는 것이었다면, 욕심쟁이 혹은 탐욕법(Greedy)의 경우 각 단계마다 현재 최선의 방법만을 선택하는 것을 의미한다. 다만 늘 현재의 최선의 해답만을 선택하므로, 앞으로 남은 선택지들에 대한 사항은 고려하지 않게 되는데 이로..

원문링크 : 욕심쟁이 알고리즘(Greedy Algorithm)