다음 문제를 해결하기 위한 알고리즘 관련 설명으로 옳은 것은?○ n개의… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지

1[7급 국가직 알고리즘] 23년 1회차

다음 문제를 해결하기 위한 알고리즘 관련 설명으로 옳은 것은?○  $n$ 개의 물건은 각기 고유의 무게와 가치를 갖는다.
○ 물건은 나눌 수 없으며, 선택한 물건은 통째로 넣는다.
○ 배낭 내 물건들의 총 무게는 배낭 용량을 초과할 수 없다.
○ 최대의 가치를 갖도록 한정된 용량의 배낭에 물건을 넣는다.

탐욕 알고리즘을 사용할 경우 시간 복잡도는  $O(n)$ 이다.

탐욕 알고리즘은 문제에 대한 최적해를 계산할 수 없다.

동적 프로그래밍 알고리즘은 가치÷무게(무게당 가치)를 사용한다.

동적 프로그래밍 알고리즘은 힙(heap)을 구성하여 최적해를 탐색한다.

해설

물건을 쪼갤 수 없는 0-1 배낭 문제에서 탐욕 알고리즘은 최적해를 보장하지 못한다.

무게당 가치가 큰 순으로 담는 탐욕 전략은 물건을 쪼갤 수 있는 분할 가능 배낭 문제에서만 최적이며, 0-1 배낭은 동적 프로그래밍(또는 분기 한정법)으로 최적해를 구한다.

예: 용량 50에 (무게 10, 가치 60), (20, 100), (30, 120)이면 무게당 가치 순 탐욕은 160을 얻지만 최적은 뒤의 두 물건을 담은 220이다.

탐욕 알고리즘도 무게당 가치로 정렬해야 하므로 $O(n\log_2(n))$ 이 들며 $O(n)$ 이 아니다.
무게당 가치를 기준으로 고르는 것은 탐욕 알고리즘의 방식이며, 동적 프로그래밍은 물건 수와 용량별 최대 가치 표를 채운다.
힙(우선순위 큐)으로 유망한 노드부터 탐색하는 것은 분기 한정법이며, 동적 프로그래밍은 표를 사용한다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 알고리즘] 23년 1회차 25문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요

비슷한 기출

7급 국가직 알고리즘 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→