이전 포스팅
이전 포스팅을 공부하고 오시는 것이 이번 포스팅을 이해하는 데, 도움을 줍니다
2023.03.20 - [알고리즘 분석 및 데이터 구조] - 알고리즘 분석 | The Master Method | 마스터 정리
알고리즘 분석 | The Master Method | 마스터 정리
이전 포스팅 알고리즘 분석 | 힙 정렬 | 분할 정복 Divide & Conquer | 병합 정렬 Merge sort 이전 포스팅 알고리즘 분석 | Heap 힙 데이터 구조 | Heap 삽입과 삭제 이전 포스팅 https://jelong.tistory.com/entry/%EC%95%
jelong.tistory.com
탐욕 알고리즘(Greedy 알고리즘)이란?
탐욕적 방법은 문제 해결을 위해 매 순간 최적이라고 생각되는 선택을 하는 방법입니다.
예를 들어, 친구들과 아이스크림 가게에 갔다고 해요. 이 가게에서는 많은 종류의 아이스크림을 팔고 있고, 여러분은 5가지 맛을 한번에 먹을 수 있는 세트를 고를 수 있어요.
하지만, 한번에 고를 수 있는 맛이 제한되어 있기 때문에, 최고의 조합을 찾는 것이 목표예요. 탐욕적 방법을 사용하면, 여러분은 가장 좋아하는 맛부터 차례대로 고르게 될 거예요. 예를 들어, 첫 번째 맛은 초코렛, 두 번째 맛은 바닐라, 세 번째 맛은 딸기, 네 번째 맛은 민트, 그리고 다섯 번째 맛은 쿠키를 고를 수 있겠죠.
이렇게 가장 좋아하는 맛을 차례대로 골라 최고의 조합을 찾는 것이 탐욕적 방법입니다. 하지만 이 방법은 항상 최적의 해결책을 찾아내지는 못할 수도 있어요. 예를 들어, 세트가 다양한 맛들이 조화롭게 어우러진 조합이 최고일 수도 있지만, 여러분은 단순히 좋아하는 맛 순서로 고르게 될 수도 있죠.
요약하면, 탐욕적 방법은 문제 해결을 위해 매 순간 최적이라 생각되는 선택을 하는 방법입니다. 이 방법은 때때로 빠르게 해결책을 찾아낼 수 있지만, 항상 최고의 해결책을 찾아내지는 못할 수도 있습니다.
시간 복잡도는 \(O(n log n)\)입니다.
그리디 알고리즘의 활용
그리디 알고리은 우리의 일상생활에서 다양한 상황에서 사용할 수 있어요. 몇 가지 예를 들어 볼게요:
동전 거스름돈: 상점에서 물건을 산 후 거스름돈을 받을 때, 가장 적은 개수의 동전으로 거슬러주려면 큰 액면가의 동전부터 줍니다. 예를 들어 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\limits_{i \in S} x_i \le W\)
총 가치는 선택된 물건들의 가치의 합에 의해 결정됩니다:
\(\sum\limits_{i \in S} b_i(x_i / w_i)\)
FKP 예시
분할 배낭 문제(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 ≈ 2.33\)
(4, 9)의 가치 대비 무게: \(9 / 4 ≈ 2.25\)
(5, 9)의 가치 대비 무게: \(9 / 5 ≈ 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이 되는 경우입니다.