목록2025/03/01 (1)

데이터 분석 기술 블로그

탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘"현재 단계에서 가장 최적의 선택을 반복하여 최종 최적해를 구하는 알고리즘"각 단계에서 최선의 선택을 하는 것이 전체적으로도 최선이라는 보장이 필요함DP와 달리, 이전 선택을 고려하지 않고 즉각적인 최적 선택을 수행대표적인 예제: 거스름돈 문제, 최소 신장 트리(Prim, Kruskal), 최단 경로(Dijkstra)탐욕 알고리즘 동작 원리현재 단계에서 가장 좋은 선택(탐욕적 선택, Greedy Choice)을 함선택한 결과를 확정하고, 다음 단계에서도 동일한 방식으로 진행최종 해답이 전체적으로 최적해인지 확인# Pseudo Code_거스름돈 문제FUNCTION GreedyChange(money, coins): coins.sort(reverse=True) # 동전 내림차순 정렬 ..
데이터 사이언스/알고리즘 2025. 3. 1. 14:12
이전 Prev 1 Next 다음