그리디 - 3. 다양한 그리디 문제 연습

📌 3. 다양한 그리디 문제 연습

✅ 학습 목표

이번 단원에서는 다양한 유형의 그리디 알고리즘 문제를 연습하면서 문제 해결 능력을 향상하고, 논리를 정리하는 연습을 진행합니다.

1. 그리디 알고리즘이 다양한 문제에 적용되는 방식 이해
2. 문제를 해결하는 과정에서 논리를 정리하고 최적의 선택을 하는 연습
3. 그리디 알고리즘이 적용 가능한 문제를 판단하는 능력 기르기

---

✅ 연습 문제

1️⃣ 회의실 배정 문제

여러 개의 회의가 있고, 한 개의 회의실에서 진행해야 합니다.
회의 시간이 겹치지 않도록 최대한 많은 회의를 배정하려면 어떻게 해야 할까요?

문제 해결 방법 (그리디 알고리즘)

• 회의를 빨리 끝낼수록 다음 회의를 배정할 수 있는 기회가 많아짐.
• 따라서, 종료 시간이 가장 빠른 회의부터 선택하면 가장 많은 회의를 배정할 수 있음.

예제

회의 번호	시작 시간	종료 시간
1	1	4
2	3	5
3	0	6
4	5	7
5	3	8
6	5	9
7	6	10
8	8	11
9	8	12
10	2	13

최적의 선택 과정

1. 종료 시간이 가장 빠른 회의 선택 → (1,4)
2. 겹치지 않는 회의 중 가장 빠른 종료 시간 선택 → (5,7)
3. 반복하여 최적해 찾기 → (8,11) 등

---

2️⃣ 배낭 문제 (Fractional Knapsack)

무게 제한이 있는 배낭에 가치를 최대화하면서 물건을 담아야 하는 문제입니다.
단, 아이템을 쪼갤 수 있음 → 무게 비율에 따라 나눠서 담을 수 있음.

문제 해결 방법 (그리디 알고리즘)

• 각 아이템의 "가치 대비 무게 비율 (value/weight)" 을 계산.
• 비율이 높은 순서대로 배낭에 담기.
• 남은 공간에 맞게 아이템을 쪼개서 넣기.

예제

아이템	무게	가치	가치 대비 무게 비율
A	10	60	6.0
B	20	100	5.0
C	30	120	4.0

배낭 용량이 50이라면,

• A (10kg) + B (20kg) + C (20kg 일부) 선택
• C는 2/3만큼(20kg) 넣음 → 총 가치 = 240

---

3️⃣ 큰 수 만들기

주어진 숫자 리스트에서 K개의 숫자를 제거하여 가장 큰 수를 만들기.

문제 해결 방법 (그리디 알고리즘)

• 숫자를 왼쪽에서 차례로 보면서 더 작은 숫자를 제거.
• 즉, 앞자리 숫자가 최대한 크도록 유지하는 것이 핵심.

예제

입력: 1924, K = 2
출력: 94  (1과 2를 제거)

입력: 4177252841, K = 4
출력: 775841  (4172 제거)

📌 핵심 원리

• 앞에서부터 탐색하며, 현재 숫자가 뒤 숫자보다 작다면 제거.
• 단, 제거할 수 있는 K개의 숫자를 초과하지 않도록 제한.

---

✅ 정리

1. 회의실 배정 문제 → 빨리 끝나는 회의부터 선택하여 최대 회의 배정.
2. 배낭 문제 (Fractional Knapsack) → 가치 대비 무게 비율이 높은 것부터 선택하여 배낭 채우기.
3. 큰 수 만들기 → 앞자리 숫자가 최대한 크도록 유지하며 작은 숫자 제거.