알고리즘 분석 | Greedy 알고리즘 쉽게 이해하기 | Fractional Knapsack Problem(분수 배낭 문제)

이전 포스팅

이전 포스팅을 공부하고 오시는 것이 이번 포스팅을 이해하는 데, 도움을 줍니다

2023.03.20 - [알고리즘 분석 및 데이터 구조] - 알고리즘 분석 | The Master Method | 마스터 정리

알고리즘 분석 | The Master Method | 마스터 정리

---

탐욕 알고리즘(Greedy 알고리즘)이란?

탐욕적 방법은 문제 해결을 위해 매 순간 최적이라고 생각되는 선택을 하는 방법입니다. 

Fig. 1. 5가지 맛 아이스크림

예를 들어, 친구들과 아이스크림 가게에 갔다고 해요. 이 가게에서는 많은 종류의 아이스크림을 팔고 있고, 여러분은 5가지 맛을 한번에 먹을 수 있는 세트를 고를 수 있어요.

하지만, 한번에 고를 수 있는 맛이 제한되어 있기 때문에, 최고의 조합을 찾는 것이 목표예요. 탐욕적 방법을 사용하면, 여러분은 가장 좋아하는 맛부터 차례대로 고르게 될 거예요. 예를 들어, 첫 번째 맛은 초코렛, 두 번째 맛은 바닐라, 세 번째 맛은 딸기, 네 번째 맛은 민트, 그리고 다섯 번째 맛은 쿠키를 고를 수 있겠죠.

이렇게 가장 좋아하는 맛을 차례대로 골라 최고의 조합을 찾는 것이 탐욕적 방법입니다. 하지만 이 방법은 항상 최적의 해결책을 찾아내지는 못할 수도 있어요. 예를 들어, 세트가 다양한 맛들이 조화롭게 어우러진 조합이 최고일 수도 있지만, 여러분은 단순히 좋아하는 맛 순서로 고르게 될 수도 있죠.

 

요약하면, 탐욕적 방법은 문제 해결을 위해 매 순간 최적이라 생각되는 선택을 하는 방법입니다. 이 방법은 때때로 빠르게 해결책을 찾아낼 수 있지만, 항상 최고의 해결책을 찾아내지는 못할 수도 있습니다.

시간 복잡도는 $O(nlogn)$입니다.

---

 

그리디 알고리즘의 활용

그리디 알고리은 우리의 일상생활에서 다양한 상황에서 사용할 수 있어요. 몇 가지 예를 들어 볼게요:

 

동전 거스름돈: 상점에서 물건을 산 후 거스름돈을 받을 때, 가장 적은 개수의 동전으로 거슬러주려면 큰 액면가의 동전부터 줍니다. 예를 들어 500원, 100원, 50원, 10원 동전이 있다면, 500원부터 최대한 많이 사용하고, 그 다음 100원, 50원, 10원 순서로 거슬러 줄 수 있죠.

시간 관리: 하루 일과를 계획할 때, 가장 중요한 일부터 처리하고, 남은 시간에 차례대로 덜 중요한 일을 처리하는 방법을 사용할 수 있어요. 이렇게 하면 시간을 효율적으로 활용할 수 있죠.

여행 경로 계획: 여행지를 방문할 때, 가장 가까운 관광지부터 차례대로 방문하는 것이 시간과 에너지를 절약할 수 있어요. 이 경우, 가장 가까운 관광지를 찾아내는 것이 탐욕적 방법인 셈이죠.

할인 상품 구매: 쇼핑을 할 때, 할인율이 가장 높은 상품부터 구매하여 예산을 절약하는 것도 탐욕적 방법을 사용한 사례입니다.

---

 

Fractional Knapsack Problem(FKP)

목표: 총 무게 $W$를 초과하지 않으면서 최대 이익을 갖는 부분 집합을 찾기:

분할 가능 배낭 문제(FKP)에서는 각 항목의 임의의 비율, $x_i$를 취할 수 있습니다.

즉, 해결책은 $x_i$ 값들의 집합으로, 이들 값들이 다음 조건을 만족합니다.

$0\le x_i\le w_i$ for all $i$, and

$\sum _{i\in S}{x}_i\le W$ 

총 가치는 선택된 물건들의 가치의 합에 의해 결정됩니다:

$\sum _{i\in S}{b}_i(x_i/w_i)$

---

FKP 예시

Fig. 2. https://en.wikipedia.org/wiki/Knapsack_problem

분할 배낭 문제(Fractional Knapsack Problem, FKP)는 배낭 문제의 한 종류로, 물건을 쪼갤 수 있다는 가정 하에 최대 가치를 찾는 문제입니다. 

 

먼저, 여러분이 다음과 같은 물건들을 가지고 있다고 가정해봅시다:

 

ex ) $w_i=3$, $x_i=7$ 는 무게 3, 가치 7를 뜻합니다

무게 3, 가치 7
무게 4, 가치 9
무게 5, 가치 9
무게 2, 가치 2

그리고 배낭의 최대 무게는 $W=6$입니다.

그리디 방법인 가치 대비 무게$b_i$가 가장 높은 물건부터 선택하는 방법을 사용해봅시다.

(3, 7)의 가치 대비 무게: $7/3\approx 2.33$
(4, 9)의 가치 대비 무게: $9/4\approx 2.25$
(5, 9)의 가치 대비 무게: $9/5\approx 1.80$
(2, 2)의 가치 대비 무게: $2/2=1.00$

1. 가치 대비 무게가 가장 높은 물건은 (3, 7)이므로, 우선 이것을 선택합니다. 이제 배낭에 남은 공간은 6 - 3 = 3입니다.

2. 다음으로 가치 대비 무게가 높은 (4, 9)를 선택하려고 하지만, 배낭에 담을 수 있는 여유 무게가 3으로 부족합니다. 그러므로 이 물건은 선택할 수 없습니다.

3. 세 번째로 가치 대비 무게가 높은 (5, 9)도 마찬가지로 배낭에 담을 수 없습니다.

4. 마지막으로, (2, 2)를 선택할 수 있습니다. 배낭에 남은 공간은 3이므로, 이 물건을 담을 수 있습니다. 이제 배낭에 남은 공간은 3 - 2 = 1이며, 더 이상 담을 수 있는 물건이 없습니다.

 

결과적으로 그리디 방법을 사용하면 (3, 7)과 (2, 2)를 선택하게 되어, 총 가치는 7 + 2 = 9가 됩니다. 

이 문제에서 그리디 방법은 최적해를 찾아내지 못했습니다. 최적해는 (4, 9)와 (2, 2)를 선택하여 총 가치가 11이 되는 경우입니다.

---