그리디 알고리즘 Greedy Algorithm
의미,쓰임
글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘
- 바로 눈앞의 이익만을 좇는 알고리즘(로컬 최적해 Locally Optimum Solution 를 찾음)
- 각 스텝에서의 Local optimum을 선택하면 global optimum에 도달한다고 믿음
- 입력 데이터간의 관계도 고려하지 않고 수행 과정에서 “욕심을 내어“ 최대값, 혹은 최소값을 가진 데이터를 선택
- 대부분의 경우에는
뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다.- 대부분의 문제들은 이런 로컬 최적해 Locally Optimum Solution 를 찾는 탐욕스런 방법으로는 문제를 해결할 수 없다
- 그러나 합리적인 시간 내에 최적에 가까운 답을 찾을 수 있다는 점에서 매우 유용
- 그리디 알고리즘은 최적화 문제를 대상으로 함
- 최적해를 찾을 수 있으면: 그것을 목표로 삼음
- 최적해를 찾기 어려운 경우: 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼음
특징
탐욕 선택 속성 Greedy Choice Property 을 갖고 있는 최적 부분 구조 Optimal Substructure의 2가지 조건을 만족하면 최적해를 찾을 수 있다
- 탐욕 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않는 것
- 다시 말해 그리디 알고리즘은 선택을 다시 고려하지 않는다.
- 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우more learn
두 조건이 만족하지 않더라도 그리디 알고리즘은 정답을 근사하게 찾는 용도로 활용 가능
- 대부분의 경우 계산 속도가 빠르므로 매우 실용적
사용
- 최단 경로 문제를 풀이하는 다익스트라 알고리즘
- 대표적인 그리디 알고리즘의 예로서 최적해 찾기 가능
- 허프만 코딩 Huffman Coding
- 압축 알고리즘
- 알고리즘 허프만 트리를 빌드할 때 그리디 알고리즘을 사용하며, 마찬가지로 최적해가 보장된다.
- 머신러닝 분야에 서는 의사결정 트리 Decision Tree 알고리즘으로 유명한 ID3 알고리즘이 그리디 알고리즘 이다.
- 항상 그때 그때 최선의 답을 찾아 트리를 빌드해 나간다.
- 물론 이 경우는 최적에 가까운 답을 찾을 수 있지만, 반드시 최적해를 찾는 것은 아니다.
그리디 알고리즘vs다이나믹 프로그래밍
최적 부분 구조 문제를 푼다는 점에서의 차이
서로 풀 수 있는 문제의 성격이 다르며 알고리즘의 접근 방식 또한 다르다.
- 다이나믹 프로그래밍: 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션 Globally Optimum Solution 에 대한 선택
- 그리디 알고리즘: 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태
서로 반대 방향으로 접근하는 구조
그렇다면 여기서는 그리디 알고리즘을 중심으로 풀 수 있는 문제, 다이나믹 프로그래밍 으로 풀어야 하는 문제, 그리디 알고리즘으로는 풀 수 없는 문제들에 대해 차례대로 살펴 보자
배낭 문제 Knapsack Problem
조합 최적화 Combinatorial Optimization 분야의 매우 유명한 문제
- 배낭에 담을 수 있는 무게의 최댓값(15kg)이 정해져 있고
- 각각 짐의 가치($ 단위)와 무게(kg 단위)가 있는 짐들을 배낭에 넣을 때
- 가치의 합이 최대가 되도록, 즉 $(달러)의 가치가 최대가 되도록 짐을 고르는 방법을 찾는 문제
분할 가능 배낭 문제 Fractional Knapsack Problem
같이 짐을 쪼갤 수 있는 경우
- 그리디 알고리즘으로 해결
solution
이 경우 단가가 가장 높은 짐부터 차례대로 채워나감
① C의 단가가 2.5달러로 가장 높으므로, C, B, E, D 순으로 총 8kg의 짐을 배낭에 담음
② 마지막 남은 7kg: A의 만큼을 쪼개서 배낭에 그리디 알고리즘으로 담는다.
③ 이렇게 하면 17.3 이라는 최적해를 찾을 수 있다.
[이 부분을 코드로 구현]
1) 짐 cargo 를 ‘(가격, 무게)’의 튜플 리스트로 정의
2) 함수 fractional_knapsack()호출
cargo = [ (4, 12), (2, 1), (10, 4), (1, 1), (2, 2), ]
r = fractional_knapsack(cargo)
3) 단가를 계산하고 역순으로 정렬
- 앞서 단가 기준으로 알고리즘을 설명한 그대로 구현하기 위해
- 즉 가장 단가가 높은 짐이 맨 위에 오도록 다음과 같이 구현
for c in cargo: pack.append((c[0] / c[1], c[0], c[1])) pack.sort(reverse=True)
4) 단가 순으로 그리디 알고리즘으로 계산
total_value: float = 0
for p in pack:
if capacity - p[2] >= 0:
capacity -= p[2]
total_value += p[1]
else:
fraction = capacity / p[2]
total_value += p[1] * fraction
break
전체 코드
def fractional_knapsack(cargo):
capacity = 15
pack = []
# 단가 계산 역순 정렬
for c in cargo:
pack.append((c[0] / c[1], c[0], c[1]))
pack.sort(reverse=True)
# 단가 순 그리디 계산
total_value: float = 0
for p in pack:
if capacity - p[2] >= 0:
capacity -= p[2]
total_value += p[1]
else:
fraction = capacity / p[2]
total_value += p[1] * fraction
break
return total_value
이처럼 구현했을때 total_value 는 17.3 을 구할 수 있다. 앞서 알고리즘을 설명했을 때와 동일한 정답이다. 그러나 이 문제에서 만약 짐을 쪼갤 수 없다면 지금까지 실행한 방식 대로 단가 순으로 배치해선 안 된다. 이와 같이 짐을 쪼갤 수 없는 0-1 배낭 문제는 23장 632페이지에서 풀이해본다.
분할 불가 배낭 문제
같이 짐을 쪼갤 수 없는 경우
- 다이나믹 프로그래밍으로 해결.
more learn
=== 다시고치지 동전 바꾸기 문제 또 다른 유명한 문제로 동전 바꾸기 문제 Coin-Change Problem 가 있다. 동전의 액면이 10원, 50원, 100원처럼 증가하면서 이전 액면의 배수 이상이 되면 그리디 알고리즘으로 풀 수있다. 우리나라 동전은 항상 배수 이상이므로 그리디로 풀 수 있다. 예를 들어 160원을 거슬러 준다면 10원짜리 16개보다는, 100원짜리 하나, 50원짜리 하나, 10원짜리 하나 로, 각각의 동전을 최대한 활용하는 그리디한 방법이 가장 작은 동전 개수로 거슬러줄 수있는 방법이다. 그런데 만약 다른 나라에 갔더니 80원짜리 동전이 더 있다고 치자. 이 경우 더 이상 그리 디하게 풀 수 없다. 160원을 거슬러줘야 한다면 80원짜리 2개가 정답인데 그리디 알고리 즘으로는 100원부터 선택하게 될 것이고 이렇게 하면 80원 2개로 풀이할 수 없기 때문이 다. 이 경우 앞서 0-1 배낭 문제와 마찬가지로 다이나믹 프로그래밍으로 풀어야 한다. 가장 큰 합 세 번째로는, 그리디 알고리즘의 실패 사례를 살펴보자. 노드를 계속 더해가다가 마지막에 가장 큰 합이 되는 경로를 찾는 문제다. 일례로 그림 21-2를 살펴보자. 그림 21-2 잘못 찾은 가장 큰 합 5 7부터 시작해 최종적으로 가장 큰 합을 만들기 위해서는 간선으로 연결된 2가지 선택지중 더 큰 수를 계속 더해나가면 될 것 같다. 그림 21-2는 전형적인 그리디 알고리즘의 형태로, 매번 가장 큰 값을 취해 나가면 7 -> 12 -> 6을 이어서 선택하게 된다. 그런데이 경우 합은 25에 불과하다. 만약 7에서 3을 택하고 99를 택하면 무려 109가 될 수 있다. 그러나 그리디 알고리즘으로는 99를 발견할 수 없다. 7은 3과 12 중에서 절대로 3을 택하지 않을 것이기 때문이다. 이 문제는 이진 트리를 정렬한다든지 등의 추가 작업을 하지 않는 한, 그리디 알고리즘으로는 풀이할 수 없다. 이제 그리디 알고리즘으로 풀 수 있는 다른 문제를 살펴보자.