그리디 알고리즘으로 최적의 해가 보장되지 않는 것은? | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지

그리디로 최적해가 보장되지 않는 것은 0-1 배낭 문제이다.
물건을 쪼갤 수 없으므로 단위 무게당 가치가 큰 순으로 담으면 남는 용량을 낭비해 최적을 놓칠 수 있어, 동적 계획법으로 풀어야 한다. 물건을 쪼갤 수 있는 분할 배낭 문제는 그리디로 최적해를 얻는다.
허프만 코딩은 빈도가 가장 작은 두 노드를 반복 병합하는 그리디로 최적 접두 코드를 만든다.
최소 신장 트리는 크루스칼·프림 알고리즘이 가장 가벼운 안전 간선을 고르는 그리디로 최적해를 보장한다.
다익스트라 최단 경로는 간선 가중치가 음수가 아니면 거리가 가장 짧은 정점부터 확정하는 그리디로 최적해를 보장한다.