📚 상식 퀴즈 해설

Q. 컴퓨터 과학에서 "그리디 알고리즘(Greedy Algorithm)"의 주요 특징은 무엇인가요?

그리디 알고리즘(Greedy Algorithm)은 매 단계에서 현재 시점에 가장 좋아 보이는 선택을 순차적으로 내려가는 문제 해결 전략입니다. 전체적인 최적해를 고려하지 않고 각 단계의 지역적 최적해(local optimum)를 선택하며, 이 선택을 번복하지 않습니다. 거스름돈 문제가 대표적인 예입니다. 1,260원의 거스름돈을 줄 때 가장 큰 동전(500원)부터 선택하면 500+500+100+100+50+10으로 6개 동전이 최적해가 됩니다. 그리디 알고리즘은 구현이 간단하고 빠르지만, 항상 전체 최적해를 보장하지는 않습니다. 최적해를 보장하려면 탐욕적 선택 속성(greedy choice property)과 최적 부분 구조(optimal substructure)를 만족해야 합니다. 허프만 코딩, 크루스칼/프림의 최소 신장 트리, 다익스트라 최단 경로 알고리즘이 그리디가 최적해를 보장하는 유명한 사례입니다.