[Algorithm] Greedy Algorithm


Greedy Algorithm 탐욕 알고리즘


  • 매 순간 최적이라고 생각되는 해를 구해나가는 알고리즘
  • 순간순간 최적이라고 생각되는 해를 구해나가기 때문에 보다 빠르게 최적에 가까운 값을 구하기 위해 사용되지만, 그 해가 무조건 최적이 아닐 수도 있기 때문에 상황에 맞게 잘 활용 해야 함
    • (특정한 상황일 경우 그리디 알고리즘도 최적의 해를 보장해 줄 수도 있음)
  • 대표적으로 그리디 알고리즘을 응용한 알고리즘으로는 다익스트라 알고리즘, 허프만 코드, 크러스컬 알고리즘 등이 있음

대표적인 그리디 알고리즘을 활용한 문제

가장 적은 동전의 수

  • 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현
coin_list = [500, 100, 50, 1]

def min_coin_count(value, coin_list):
    total_coin_count = 0
    details = list()
    coin_list.sort(reverse=True)
    for coin in coin_list:
        coin_num = value // coin
        total_coin_count += coin_num
        value -= coin_num * coin
        details.append([coin, coin_num])
    return total_coin_count, details
가장 적은 동전의 수를 구하는 코드 구현


부분 배낭 문제

  • 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
  • 각 물건은 무게(w)와 가치(v)로 표현될 수 있음
    • 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음, 그래서 Fractional Knapsack Problem 으로 부름
    • Fractional Knapsack Problem 의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재 (0-1 Knapsack Problem)
      • (이 경우에는 그리디 알고리즘이 아닌 다이나믹 프로그래밍으로 문제를 해결 해야 함)
가방 (i)가방1가방2가방3가방4가방5
무게 (w)1015202530
가치 (v)10121085
data_list = [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]

def get_max_value(data_list, capacity):
    data_list = sorted(data_list, key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0
    details = list()
    
    for data in data_list:
        if capacity - data[0] >= 0:
            capacity -= data[0]
            total_value += data[1]
            details.append([data[0], data[1], 1])
        else:
            fraction = capacity / data[0]
            total_value += data[1] * fraction
            details.append([data[0], data[1], fraction])
            break
    return total_value, details
부분 배낭 문제를 구하는 코드 구현


탐욕 알고리즘의 한계

  • 탐욕 알고리즘은 반드시 최적의 해를 구할 수 있는 것은 아니기 때문에 근사치 추정에 활용
  • 최적의 해에 가까운 값을 구하는 방법 중의 하나이기 때문에 한계가 존재


출처 : https://www.fun-coding.org/Chapter19-greedy-live.html
그리디 알고리즘의 한계


  • 시작 노드에서 시작해서 가장 작은 값을 찾아 leaf node 까지 가는 경로를 찾을 때
    • 그리디 알고리즘 적용시 시작 -> 7 -> 12 를 선택하게 되므로 7 + 12 = 19
    • 하지만 실제 가장 작은 값은 시작 -> 10 -> 5 이며, 10 + 5 = 15 가 가장 작은 값

외판원 순회 문제 (TSP : Traveling Salesman Problem)

  • n개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능한 짧은 경로를 찾는 알고리즘
  • 그리디 알고리즘의 해가 최적의 해가 아니라는 것을 보여주는 대표적인 예시 중 하나



참고

잔재미코딩
신찬수 교수님 유튜브
나무위키






© 2021. by hminkim