그리디1 그리디 알고리즘 증명1 - Greedy stays ahead 그리디 알고리즘(greedy algorithm) 완전 탐색, 동적 계획법처럼 답을 구하는 과정을 여러 개의 단계로 나누어 답을 만들어가는 과정은 비슷하지만, 각 단계에서 가능한 모든 답을 계산하여 전체적으로 가장 좋은 답을 선택하는 것이 아니라 각 단계에서 가장 좋은 답을 선택하는 점이 완전 탐색, 동적 계획법과 다른 점이다. 외판원 순회 문제에서 동적 계획법은 현재 정점에서 갈 수 있는 정점 중에 전체 거리를 최소화할 수 있는 정점을 고르지만, 그리디 알고리즘은 단순히 현재 정점에서 다음 정점까지의 거리를 최소화하는 정점을 고른다. 그리디 알고리즘은 "답을 도출하는 과정 중 매 순간 최고의 선택을 해서 결과적으로 최적의 해를 도출하자"로 표현할 수 있다. 그런데 매 순간 최고의 선택이 항상 결과적으로 .. 2022. 7. 29. 이전 1 다음