[Algorithm] 그리디 알고리즘(Greedy Algorithm), 분할 배낭 문제(Fractional Knapsack Problem)

Algorithm - 그리디 알고리즘

대수학의 아버지 알콰리즈미, 알고리즘은 그의 이름에서 유래되었다

알고리즘은 컴퓨터 과학의 핵심 요소이다. 검색 알고리즘 덕분에 데이터의 바다에서 원하는 것을 추출할 수 있다. 정렬 알고리즘은 난잡한 데이터들을 잘 정리하여 가공할 수 있도록 만들어준다. 그래프 알고리즘은 효율적인 연결 경로를 찾는데에 필수적이다. 알고리즘 지식은 프로그래밍과 시스템 설계에서 복잡한 문제를 해결하는데 필수적이다.

---

그리디 알고리즘(Greedy Algorithm)

 

What is greedy algorithm?

 

정의

그리디 알고리즘은 항상 명확하고 즉각적인 이익이 되는 것을 선택하는 알고리즘입니다. 매 순간에 가장 이익이 되는 것을 선택하는 최적화 문제에서 사용합니다. 빠르게 구현이 가능하고 간단하게 작동하는 장점이 있습니다. 다른 말로 탐욕 알고리즘이라고도 부릅니다.

 

그리디 알고리즘을 구현하는 단계는 매우 간단합니다.

1. 해결해야 하는 문제를 정의합니다.
2. 최적의 선택을 확인합니다. 현재 상태에서 어떤 선택이 최선인지 알아냅니다.
3. 최적의 선택을 수행합니다. 최적의 선택을 수행하고 현재 상태에 변화를 적용합니다.
4. 위 단계를 반복합니다.

 

---

한계

https://www.freecodecamp.org/news/greedy-algorithms/

 

 

그리디 알고리즘은 지역적으로 선택을 합니다. 즉, 요소의 전체를 보고 판단하지 않습니다. 이러한 특징 때문에 항상 최적의 해답을 찾을 수 없다는 단점이 존재합니다.

 

예를 들어 위 그림에서 그리디 알고리즘을 적용해서 최댓값이 되는 수의 합을 찾아봅시다. 매 순간 최고의 이익을 선택하면 6 -> 4 -> 14로 총 수의 합은 24가 됩니다.

 

하지만 이는 지역적인 선택입니다. 만약 모든 요소를 고려하여 선택한다면 6 -> 3 -> 20로 총 수의 합은 29가 됩니다. 즉 그리디 알고리즘을 사용하면 요소의 순서와 같은 환경에 따라 최적의 해답을 놓칠 수 있습니다.

 

---

분할 배낭 문제(Fractional Knapsack Problem)

 

Fracional Knapsack Problem

 

그리디 알고리즘을 적용할 수 있는 유명한 문제로 분할 배낭 문제가 존재합니다. 해당 문제에 대한 설명은 아래와 같습니다.

N개의 상자가 존재한다. 각 상자는 가치와 무게 수치를 가진다. 이 상자들을 W만큼의 공간의 가방에 넣어야 한다. 각 상자들은 분할이 가능하다.

 

위 문제를 풀기위해 가능한 모든 부분집합을 고려한다면 시간 복잡도 O(2^N)과 보조 공간 O(N)이 필요합니다. 이를 그리디 알고리즘으로 접근한다면 더욱 쉽게 풀어낼 수 있습니다.

 

---

 

그리디 알고리즘으로 접근

해당 문제에 그리디 알고리즘을 사용하는 방법은 다음과 같습니다.

1. 이익과 무게의 비율을 계산하여 비율이 높은 순서대로 상자들을 정렬시킵니다.
2. 순서대로 상자를 선택합니다.

 

{{100, 20}, {60,10}, {120, 30}}의 이익과 무게를 가지는 상자들이 존재합니다. 이를 W = 50 크기의 가방에 넣어야합니다. 최적의 해를 구해봅시다.

 

우선 각 상자의 비율을 계산해야합니다. 이익 / 무게로 비율을 계산한 뒤 정렬하면 {{60,10}, {100,20}, {120, 30}}의 순서로 나열됩니다. 이제 상자들을 순서대로 선택하겠습니다.

 

첫 번째 상자를 선택하면 profit : 0 -> 60, W : 50 -> 40이 됩니다.

 

두 번째 상자를 선택하면 profit : 60 -> 160, W : 40 -> 20이 됩니다.

 

세 번째 상자는 무게가 30이기 때문에 2/3으로 나누어줍니다. 그렇다면 {80, 20}의 상자로 분할됩니다. 따라서 최종적으로 profit = 240, W = 50이라는 해를 얻을 수 있습니다.

 

 

---

 

0-1 배낭 문제(0-1 Knapsack Problem)

만약 상자를 분할할 수 없다면 어떻게 될까요? 그러한 상황에서는 문제를 그리디 알고리즘으로 풀어낼 수 없게 됩니다. 이를 0-1 배낭 문제라고 하며 동적 계획법(Dynamic Programming)과 같은 최적화 문제 풀이법을 적용해야 합니다.

 

다음 포스트에서 동적 계획법과 함께 해당 문제를 다루도록 하겠습니다.

---