CBTNow

[9급 국가직 알고리즘 2025년 9번]

다항적 시간 복잡도를 갖는 탐욕(greedy) 알고리즘으로 최적의 해를 구할 수 없는 것은?
알고리즘
  1. ①부분 배낭(fractional knapsack) 문제
  2. ②한 정점에서 다른 정점으로의 최단 경로 탐색 문제
  3. ③이진 트리의 최대합 경로 찾기 문제
  4. ④최소 신장 트리(MST, Minimum Spanning Tree) 생성 문제
정답 ③

출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)