[자료구조&알고리즘 | WEEK04] 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘이란?

---

그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다.

 

그리디 알고리즘(Greedy Algorithm)란 바로 눈 앞의 이익만을 쫓는 알고리즘이다. 대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다.

 

그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다. 이러한 특성때문에 '욕심쟁이 알고리즘'이라는 별명이 붙은 알고리즘이기도 하다.

 

아래 이미지를 보면 큰 값을 찾기 위한 '그리디 알고리즘의 동작방식과 실제 큰 값은 다르다.'는 것을 알 수 있다.

(진짜 욕심쟁이네.. 벌 받은거임)

 

그리디 동작방식과 실제 결과 값은 다름

 

대부분의 문제들은 이런 로컬 최적화(Locally Optimum Solution)를 찾는 탐욕스런 방법으로는 문제를 해결할 수 없지만 합리적인 시간 내에 최적에 가까운 답을 찾을 수 있다는 점에서 유용한 알고리즘이다.

로컬 최적화(Locally Optimum Solution)는 아래 '그리디 알고리즘 VS 다이나믹 프로그래밍' 비교에 설명함

 

어떤 경우에 잘 동작하는가 | 그리디 알고리즘의 특성

그리디 알고리즘이 잘 작동하는 문제들은 탐욕 선택 속성(Greedy Choice Property)을 갖고 있는 최적 부분 구조(Optimal Substructrue)인 문제들이다.

 

💡

탐욕 선택 속성(Greedy Choice Property)이란?

앞의 선택이 이후 선택에 영향을 주지 않는 것을 말한다.

즉, 한번의 선택이 다음 선택에서는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다.

(최단 거리 문제 - 다익스트라 알고리즘과 유사함)

 

💡

최적 부분 구조(Optimal Substructrue)란?

문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다.

 

이렇게 2가지 조건을 만족하면 최적해를 찾을 수 있다. 하지만 그렇지 않더라도 그리디 알고리즘은 정답을 근사하게 찾는 용도로 활용할 수 있으며, 대부분의 경우 연산 속도가 빠르므로 매우 실용적이다.

 

추가 설명 - 최적 부분 구조

최적 부분 구조는 말이 좀 와닿지 않아서 나무위키 - 그리디 알고리즘를 참고하였다.
아래 이미지에서 서울에서 대구를 경유해 부산까지 가는 경로를 최적의 방법으로 계산하려면 어떻게 해야할까?

1. 우선 서울에서 대구까지 총 3가지의 경로가 있는데(250km, 200km, 300km), 우리는 당연히 200km를 고르면 된다.(부분 문제에 대한 최적 해결 방법)
2. 대구에서 부산까지도 총 3가지의 경로(100km, 80km, 120km) 중 80km를 선택해 총 280km를 선택하면 된다.(부분 문제에 대한 최적 해결 방법)

이처럼 '서울에서 대구를 경우해 부산까지 최적의 경로'라는 큰 문제를 풀기 위하여 위의 2가지 부분 문제들을 해결해 나가는 것을 최적 부분 구조라고 한다.

 

 

이전에 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘을 배우고, 문제를 풀면서 최단 경로 문제를 해결하는 '다익스트라 알고리즘'을 공부한 적이 있는데 이 알고리즘이 대표적인 그리디 알고리즘을 활용하는 문제이다. 최단 경로를 찾기 위해서 그때 그때마다 최단 경로를 선택하면 최단 경로가 된다는 점에서 각각의 문제마다 '최적의 해를 선택한다.'가 그리디 알고리즘의 핵심이다.

 

이외에도 그리디 알고리즘은 다양한 분야에서 활용되는데,

1. 압축 알고리즘인 허프만 코딩(Huffman Coding)알고리즘
   • 허프만 트리를 빌드할 때 그리디 알고리즘을 사용하며, 최적해가 보장된다.
2. 머신러닝 분야에서는 의사결정 트리(Decision Tree) - ID3 알고리즘
   • 그때 그때 최선의 답을 찾아 트리를 빌드해 나간다.

 

다시 한번 강조하면 그리디 알고리즘은 무조건 최적의 해를 구한는 것은 아니고(최적의 해를 구할 수도 있음), 정답(목표)에 근사한 값을 도출할 수 있다.

 

그리디 알고리즘 VS 다이나믹 프로그래밍

---

두 개의 알고리즘 모두 최적 부분 구조로 문제를 해결해 간다는 점에서 비슷해 보이지만, 서로 해결할 수 있는 문제도 다르고, 접근법도 다르다.

최적 부분 구조는 앞의 '다이나믹 프로그래밍' 포스팅에서 언급함

 

다이나믹 프로그래밍

다이나믹 프로그래밍에서는 하위 문제들을 해결해 나가면서 최적의 솔루션을 찾은 다음, 이 결과들을 활용하여 최종적으로 큰 문제를 효율적으로 해결한 알고리즘이라고 할 수 있다. 이것을 전역 최적 솔루션(Globally Optimum Solution)이라고 한다. 즉, 목표한 문제를 해결하기 위해 이전의 값들을 활용하므로(활용하지 않을 수도 있음) 전역 최적 솔루션이라고 한다.

 

그리디 알고리즘

그리디 알고리즘은 각 단계마다 최적의 해를 찾는 문제로 로컬 최적화(Locally Optimum Solution)라고 한다.

관점을 범위로 봤을 때도 다이나믹 프로그래밍은 전체의 결과에 대해서 값을 판단하는 반면에, 그리디 알고리즘은 범위를 줄여가면서(각 단계마다 최적의 해를 찾으며 넘어가므로) 진행되므로 성격 자체가 다르다.

 

문제 풀이 - 배낭 문제

---

배낭 문제(Knapsack Problem)는 조합 최적화(Combinatorial Optimization) 분야에서 매우 유명한 문제라고 한다. 배낭 문제는 쉽게 말해서 허용 용량(capacity) 범위 내에서 각각 짐의 가치($)와 무게를 고려해 가장 최적의 해를 찾는 문제인데, 이번 문제에서는 짐의 무게를 쪼갤 수 있을 때(최대한의 이득을 얻기 위해) 그리디 알고리즘을 사용할 수 있다. 만약 짐의 무게를 쪼갤 수 없을 때는 '이전의 값을 재활용하여 최적의 해를 구하는 다이나믹 프로그래밍'을 사용하여야 한다.

 

문제 해결 전략

1. 최대한의 이득을 얻을 수 있도록 즉, 돈을 최대한 많이 벌어가는게 이번 문제에서 최적의 해를 구하는 목표이다.
2. 따라서 단가가 가장 높은 짐부터 담아가면 된다.(최적의 해를 구하기 위해)
3. 가장 단가가 높은 짐들을 순차적으로 넣은 뒤, 남은 짐 중에서 가장 단가가 높은 짐의 무게를 쪼개어(해당 문제가 그리디 알고리즘이 가능한 이유) 짐을 실은 만큼 값을 산정한다.

 

위의 문제 해결 전략을 코드로 나타내면 아래와 같다.
여기서 다시 강조하고 싶은 부분은 짐을 쪼갤 수 있기에, 매번 계산할 때마다 최적의 해를 고르는 그리디 알고리즘을 사용할 수 있는 것이지, 짐을 쪼갤 수 없고 최적의 해를 구하려면 전역 최적 솔루션(Globally Optimum Solution)인 '다이나믹 프로그래밍'을 사용하여야 한다.

"""
그리디 알고리즘
최대 이익을 얻기 위해서 무게를 어떻게 담아야 하는가
"""

# 배낭에 넣을 수 있는 짐(가격, 무게)
cargo = {
    (4, 12),
    (2, 1),
    (10, 4),
    (1, 1),
    (2, 2)
}


def fractional_kanpsack(cargo):
    capacity = 15  # 배낭에 들어갈 수 있는 최대 용량
    pack = []
    # 단가 계산 역순 정렬(가장 이득을 많이 취할 수 있도록)
    for c in cargo:
        pack.append((c[0] / c[1], c[0], c[1]))
    pack.sort(reverse=True)

    total_value = 0
    # 단가가 높은 순으로 계산(그리디 계산)
    for p in pack:
        if capacity - p[2] >= 0:
            capacity -= p[2]
            total_value += p[1]
        # 무게 전체가 들어가지 않을 때
        # 즉, 짐을 분할해서 넣을 수 있을 때(이럴 때 그리디 알고리즘이 사용될 수 있다.)
        else:
            fraction = capacity / p[2]
            total_value += fraction * p[1]
            break

    return total_value


print(fractional_kanpsack(cargo))

 

---

Ref

파이썬 알고리즘 인터뷰

나무위키 - 그리디 알고리즘

Greedy Algorithms