이 포스트에서는 탐욕 알고리즘과 동적 프로그래밍 방법의 차이점을 이해할 것입니다.
그리디 알고리즘
솔루션을 부분적으로 단계별로 구축하는 알고리즘 패러다임입니다. 다음 단계는 가장 분명하고 즉각적인 이점을 제공하도록 선택됩니다.
- 지역 최적 값 선택과 관련된 문제는 문제에 대한 전역 최적 값/솔루션을 선택하는 데 도움이 됩니다. 탐욕스러운 알고리즘과 관련된 문제를 먹었습니다.
- 탐욕적인 알고리즘이 최적의 솔루션으로 이어질 것이라는 보장은 없습니다.
- 문제의 모든 단계에서 최적의 선택이 이루어집니다. 즉, 로컬 최적 솔루션입니다.
- 이전 솔루션/값을 되돌리거나 변경할 필요가 없으므로 메모리 사용 면에서 효율적입니다.
- 일반적으로 동적 프로그래밍 기술에 비해 빠릅니다.
- 예:O(ELogV + VLogV) 시간이 걸리는 Dijkstra의 최단 경로 알고리즘.
- 그리디 알고리즘의 해는 전진 방식으로 계산되며 이전 값/해를 방문하거나 변경하지 않습니다.
동적 프로그래밍
나중에 필요할 때 다시 계산할 필요가 없도록 하위 문제의 결과를 저장하는 데 도움이 되는 최적화 기술입니다. 미리 계산된 집합에서 추출할 수 있습니다. 지수 복잡도에서 다항 복잡도로 시간 복잡도를 줄입니다.
- 예:재귀 솔루션은 컴퓨팅을 통해 동적 프로그래밍 문제로 전환될 수 있습니다.
- 여기서 모든 단계에서 내리는 결정은 현재 당면한 문제와 이전에 풀었던 합 문제의 해를 고려하여 이루어집니다. 이것은 최적의 값/솔루션을 계산하는 데 사용됩니다.
- 동적 프로그래밍 문제의 솔루션이 최적의 솔루션임을 보장합니다.
- 여기서 선택한 최적의 솔루션은 글로벌 최적의 솔루션입니다. 이전에 계산된 상태 값을 저장하는 데 사용되었을 특정 공식을 사용합니다.
- 암기에는 동적 프로그래밍 테이블이 필요합니다. 이는 메모리 복잡성을 증가시킵니다.
- 비교적 느립니다.
- 예:O(VE) 시간이 걸리는 Bellman Ford 알고리즘.
- 동적 프로그래밍은 상향식 또는 하향식 접근 방식을 사용하여 솔루션을 결정하고 최적의 솔루션이 있는 작은 문제를 개발합니다.