15.6   연습 문제¶

15.6.1   개념 확인¶

1.   매번 가장 큰 동전을 고르면 항상 최선인가¶

동전의 액면가는 [1, 7, 10]이며, 목표 금액은 14다.

1. ‘남은 금액을 넘지 않는 가장 큰 액면가의 동전을 매번 고른다’는 규칙을 실행하고 선택한 동전을 적어 보자.
2. 동전을 더 적게 사용하는 방법이 있는가? 있으면 하나를 적고, 없으면 이유를 설명하라.
3. 이 결과로 해당 탐욕 전략이 어떤 동전 액면가에서든 올바르다고 할 수 있는가?

2.   배낭에 어떤 물건을 먼저 넣어야 하는가¶

용량이 4킬로그램인 배낭에 다음 물건을 넣을 수 있다. 물건의 일부만 넣어도 되며, 얻는 가치는 넣은 무게에 비례한다.

• 물건 A: 무게 4킬로그램, 가치 20
• 물건 B: 무게 3킬로그램, 가치 18

1. 두 물건의 킬로그램당 가치는 각각 얼마인가? 어느 물건을 먼저 넣어야 하는가?
2. 분할 가능한 배낭 문제의 탐욕 전략으로 배낭을 가득 채우면 최종 가치는 얼마인가?
3. 물건을 나눌 수 있고 배낭이 총무게를 제한하는 상황에서는 물건을 고를 때 총가치와 킬로그램당 가치 중 무엇을 비교해야 하는가? 이유도 설명하라.

3.   두 포인터를 다음에 어떻게 움직여야 하는가¶

칸막이 높이가 [1, 8, 6, 2, 5]일 때 양 끝에서 시작하는 두 포인터로 최대 용량을 찾는다. 용량은 ‘두 칸막이 중 더 낮은 높이 × 두 칸막이의 인덱스 차이’다.

1. 처음에는 왼쪽 포인터가 인덱스 0, 오른쪽 포인터가 인덱스 4에 있다. 현재 용량은 얼마인가? 다음에는 어느 포인터를 움직여야 하는가?
2. 1번에서 선택한 대로 한 번 움직이면 두 포인터는 각각 어느 인덱스에 있는가? 이때 용량은 얼마이며, 다음에는 어느 포인터를 움직여야 하는가?
3. 현재 두 칸막이에서 더 낮은 쪽의 포인터를 움직일 수도 있고, 더 높은 쪽의 포인터를 움직일 수도 있다. 어느 쪽을 움직여야 더 큰 용량을 얻을 가능성이 남는가? 이유는 무엇인가?

15.6.2   프로그래밍 연습¶

1.   분할 가능한 배낭 문제¶

길이가 같은 배열 wgt와 val이 주어진다. wgt[i] > 0, val[i] >= 0이며 배낭 용량은 cap >= 0이다. 각 종류의 물건은 하나씩만 있지만, 그중 일부만 넣어도 된다. 얻는 가치는 넣은 무게가 해당 물건의 총무게에서 차지하는 비율로 계산한다. 탐욕 알고리즘을 사용하여 배낭에서 얻을 수 있는 최대 총가치를 실수로 반환하라.

댓글로 의견이나 질문, 제안을 남겨 주세요