hello-algo/ko/docs/chapter_greedy/exercises.md

연습 문제

개념 확인

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

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

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

??? success "참고 답안"

1. 탐욕 방식은 `10 + 1 + 1 + 1 + 1`을 차례대로 선택하여 총 5개의 동전을 사용한다.

2. 더 적게 사용하는 방법이 있다. `7 + 7`이면 동전 2개만 필요하다.

3. 그럴 수 없다. 이 반례는 임의의 동전 액면가에서 현재 고를 수 있는 가장 큰 액면가를 매번 선택한다고 해서 반드시 최소 동전 개수를 얻는 것은 아님을 보여 준다.
    당장 가장 큰 것을 선택하면 이후에 더 좋은 조합을 만들 기회를 잃을 수 있다.

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

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

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

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

??? success "참고 답안"

1. A의 킬로그램당 가치는 `20 ÷ 4 = 5`, B의 킬로그램당 가치는 `18 ÷ 3 = 6`이다.
    따라서 단위 무게당 가치가 더 높은 B를 먼저 넣어야 한다.

2. 먼저 B를 전부 넣으면 3킬로그램을 차지하고 가치 18을 얻는다. 남은 용량 1킬로그램에는
    A를 1킬로그램 넣어 가치 5를 얻는다. 최종 가치는 `18 + 5 = 23`이다.

3. 배낭은 총무게를 제한하고 물건을 나눌 수 있으므로 단위 무게당 가치를 비교해야 한다.
    A는 총가치가 더 높지만 킬로그램당 가치는 B보다 낮다. A부터 넣어 배낭을 채우면 가치 20밖에 얻지 못한다.

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

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

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

??? success "참고 답안"

1. 현재 용량은 `min(1, 5) × (4 - 0) = 4`다. 왼쪽 칸막이가 더 낮으므로 왼쪽 포인터를 움직인다.

2. 왼쪽 포인터를 움직이면 두 포인터는 각각 인덱스 1과 4에 있다. 현재 용량은
    `min(8, 5) × (4 - 1) = 15`다. 오른쪽 칸막이가 더 낮으므로 다음에는 오른쪽 포인터를 움직인다.

3. 더 낮은 칸막이 쪽의 포인터를 움직여야 더 큰 용량을 얻을 가능성이 남는다. 더 높은 칸막이를 움직이면 두 칸막이 사이의 거리는 반드시 줄어드는 반면, 용기의 높이는 여전히 움직이지 않은 낮은 칸막이에 의해 제한되므로
    그대로이거나 더 낮아질 뿐이다. 따라서 용량은 움직이기 전보다 커질 수 없다. 낮은 칸막이를 움직여야만 더 높은 칸막이를 만날 기회가 생긴다.

프로그래밍 연습

분할 가능한 배낭 문제

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

??? tip "풀이 힌트"

1. 먼저 각 물건의 단위 무게당 가치 val[i] / wgt[i]를 계산한다. 나눗셈 결과의 소수 부분을 유지해야 한다.
2. 단위 무게당 가치가 높은 물건부터 배낭에 넣는다.
3. 남은 용량이 현재 물건의 무게보다 작으면 배낭을 정확히 채우는 만큼만 넣고 끝낸다.