안타깝고 당연하지만 이제는 코테를 무작정 풀 수는 없으니 모르는 척 그만하고 알고리즘을 하나씩 정리해야겠다.
알고리즘 수업을 2년 전 수강했지만 남은건 거의 없는 백지에서부터 채우기 목표
탐욕 알고리즘 (Greedy Algorithm)
- Greedy (탐욕적인, 욕심 많은) 알고리즘
- 최적해를 구하는 데 사용하는 근사적인 방법
- 선택의 순간마다 가장 최선이라고 생각하는 것을 선택해 최종 해답에 도달하는 방식
- 하지만, 순간(Local)의 최적해가 최종해(Global)의 최적이라는 것을 보장 불가능
탐욕 알고리즘은 말 그대로 욕심 많은 사람을 생각하면 된다.
모든 순간마다 가장 최적의 해를 선택하지만, 결국 최종적으로는 최적의 답이 될 수도 아닐 수도 있다.
단, 탐욕 알고리즘을 사용하면 최적해를 보장하진 못해도 어쨌든 효율적인 선택을 할 수는 있다.
완벽한 답이 아닌 어느 정도 근사적인 답을 원하는 경우 사용하면 실용적이다.
알고리즘
- 해 선택 (Selection Procedure) : 선택의 순간 최적의 해를 고른 후, 부분해 집합에 추가
- 적절성 검사 (Feasibility Check) : 새로운 부분해 집합이 적절한지 검사
- 해 검사 (Solution Check) : 새로운 부분해 집합이 전체의 해답이 되었다면 종료, 아니라면 과정 반복
위와 같은 절차를 통해 문제를 해결한다.
하지만 최종해가 최적이 되지 않을 수도 있으므로 일정 조건을 만족해야 탐욕 알고리즘을 사용할 수 있다.
만족 조건
- 최적 부분 구조 조건 (Optimal Substructure) : 순간의 최적해가 항상 최종의 최적해를 보장한다.
- 탐욕적 선택 속성 (Greedy Choice Property) : 각각의 값이 서로 영향을 주지 않아야 한다.
탐욕 알고리즘을 적용하기 위해서는 위의 2가지 경우를 만족해야 한다.
즉, 한 번의 선택이 다음 선택과는 무관해야 하며, 매 순간의 최적해가 항상 최종의 최적해가 되어야 한다.
그렇다면 탐욕 알고리즘은 구체적으로 어떤 문제를 해결하기에 적합할까?
배낭 채우기 문제 (Knapsack Problem)
- Greedy Algorithm과 Dynamic Programming을 사용하는 문제
- 배낭의 최대 무게 한도 내에서 가장 비싼 물건들로 채우는 방법을 구하는 문제
Q. 배낭의 총 무게가 W = 30kg일 때, 배낭이 찢어지지 않는 선에서 담은 물건의 가격 합이 최대가 되도록 하는 방법은?
| 품목 | 무게 | 값 |
| item 1 | 25kg | 10만원 |
| item 2 | 10kg | 9만원 |
| item 3 | 10kg | 9만원 |
위와 같이 물건이 존재할 때, 배낭이 넘치지 않도록 가격이 최대한 많이 나갈 수 있게 물건을 담는 방법은 무엇일까?
본인이 도둑의 입장이고, 최대한 효율적으로 비싼 물건들을 훔쳐가는 방법을 생각해야 한다고 떠올려보자
Solution 1.
가장 단순무식한 방법인 무작정 알고리즘을 사용해볼 수 있다.
가져갈 수 있는 모든 경우의 수를 다 구해 최선의 방법을 선택하는 것이다.
이렇게 되면 n개의 물건에 대해 모든 부분집합을 구해야 한다.
즉, 부분집합의 수는 2^n개이므로 O(2^N)이라는 시간 복잡도를 갖는다. 코딩 테스트에서 사용하기에는 무리가 있다.
Solution 2.
이때 탐욕 알고리즘을 적용하면 다음과 같다,
가장 가격이 비싼 물건부터 우선적으로 채우는 방법이다.
즉, 가격이 비싼 물건을 채우는 '최선의 선택'을 하고, 자리가 비어 있으면 또다시 '최선의 선택'을 하는 것이다.
하지만, 이는 최적해가 아니다.
- 탐욕 알고리즘 : item 1 --> 25kg --> 10만원
- 최적해 : item 2 + item 3 --> 20kg --> 18만원
그렇다면 단순히 가격만 보지 말고 무게 당 가치가 높은 물건부터 담는 방법을 사용하면 어떨까?
| 품목 | 무게 | 값 | 값어치 |
| item 1 | 5kg | 50만원 | 10만원/kg |
| item 2 | 10kg | 60만원 | 6만원/kg |
| item 3 | 20kg | 140만원 | 7만원/kg |
Solution 3.
이번에는 무게 당 가격이 높은 물건부터 담는 방법이다.
하지만, 마찬가지로 이는 최적해가 아니다.
- 탐욕 알고리즘 : item 1 + item 2 --> 25kg --> 110만원
- 최적해 : item 2 + item 3 --> 30kg --> 200만원
즉, 어떤 방법을 적용해도 결국 탐욕 알고리즘은 배낭 채우기 문제에서 최적해를 찾지 못한다.
Solution 4.
탐욕 알고리즘을 사용해서 해결할 수 있는 방법이 있기는 하다.
배낭 빈틈 없이 채우기 문제 (The Fractional Knapsack Problem)로, 물건의 일부를 잘라서 담는 것이다.
- 탐욕 알고리즘 : item 1 + item 3 + item 2 * 1/2 --> 30kg --> 220만원
비싼 물건부터 채우고 나머지는 물건을 나누어 채우면 당연하게도 최적해를 만족한다.
하지만 이런 식의 문제는 거의 나오지 않는다.
이러한 배낭 채우기 문제는 DP(Dynamic Programming) 알고리즘을 사용해 해결할 수 있다. (이건 나중에 ^^)
거스름돈 문제
- 동전의 개수를 가장 적게 사용해 거스름돈을 제공하는 방법은?
- 10원, 50원, 100원, 500원 --> 상위 값은 항상 하위 값의 배수
동전으로 거스름돈을 주는 문제에서 적절하게 사용할 수 있다.
동전의 종류가 4가지로 한정되어 있으며, 큰 단위의 동전이 작은 단위의 동전의 배수이기 때문이다.
(만약 동전 중 300원 단위가 포함되어 있다면 해결이 불가능하다.)
이때의 '최선의 선택'은 가장 비싼 값을 선택하는 것이다.
890원을 거슬러야 할 경우는 가장 큰 단위인 500원부터 시작해 나머지를 채우면 된다.
활동 선택 문제 (Action Selection Problem)
- 활동 시간 내 최대한 많은 활동을 하도록 선택하는 방법은?
- 각 활동은 시간이 겹칠 수 없으며, 하나의 활동이 끝나야 다른 활동을 시작할 수 있다.
위와 같이 교실이 하나일 때, 시작 시간과 종료 시간이 모두 다른 수업들을 적절히 조합해서 최대한 많은 수업을 선택하는 문제에도 탐욕 알고리즘을 사용할 수 있다.
마찬가지로 '최선의 선택'은 가장 일찍 끝나는 수업을 선택하는 것이다.
매 순간 가장 빨리 끝나는 수업을 선택한다면 그만큼 다른 수업을 들을 시간이 많아진다.
댓글