다음 문제를 해결하기 위한 알고리즘 관련 설명으로 옳은 것은?
○ 개의 물건은 각기 고유의 무게와 가치를 갖는다.○ 물건은 나눌 수 없으며, 선택한 물건은 통째로 넣는다.○ 배낭 내 물건들의 총 무게는 배낭 용량을 초과할 수 없다.○ 최대의 가치를 갖도록 한정된 용량의 배낭에 물건을 넣는다.
- ①탐욕 알고리즘을 사용할 경우 시간 복잡도는 이다.
- ②탐욕 알고리즘은 문제에 대한 최적해를 계산할 수 없다.
- ③동적 프로그래밍 알고리즘은 가치 ÷ 무게(무게당 가치)를 사용한다.
- ④동적 프로그래밍 알고리즘은 힙(heap)을 구성하여 최적해를 탐색한다.
선지를 골라 바로 채점해 보세요.
정답 ②
출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)