태그 · #kruskal-algorithm

[멀티캠퍼스] 풀스택 개발자 아카데미 (15) - Algorithm(4)

탐욕 알고리즘은 매 순간 최선의 선택을 통해 전체 최적해를 도출하는 빠르고 직관적인 전략으로, '탐욕적 선택 속성'과 '최적 부분 구조'를 만족해야 성공을 보장합니다. 거스름돈 문제나 최소 신장 트리 같은 문제에 유용하지만, 조건이 충족되지 않는 경우에는 오답을 낼 수 있어 동적 프로그래밍 등 다른 접근법이 필요합니다. 따라서 이 알고리즘을 적용할 때는 문제의 구조가 탐욕적 선택을 정당화하는지 증명하고 판단하는 통찰력이 핵심입니다.