[Algorithm] 그리디 (Greedy) 알고리즘

당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘

항상 최적의 결과를 도출하는 것은 아니지만, 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. 또한 특정한 상황에는 최적의 해를 보장할 수 있는 알고리즘이다. 

가장 대표적인 예로, 거스름돈 문제가있다.

'무조건 큰 화폐 단위부터 거슬러준다' 라는 조건하에 문제를 풀면 그리디 알고리즘은 최적의 해를 보장한다. 

'무조건 큰 경우대로' '무조건 작은 경우대로' 등 무조건적인 극단적 조건이 있다면 정렬(Sort)와 함께 사용되는 경우가 많다. 그 예시로 크루스칼 알고리즘 ( 모든 간선을 정렬한 이후 짧은 간선부터 연결하는 최소 비용 신장 트리 알고리즘) 이 있다.

프로그래머스 그리디 알고리즘 1. 체육복

def solution(n, lost, reserve):
    set_reserve = set(reserve)-set(lost)
    set_lost = set(lost)-set(reserve)
    # lost, reserve 양쪽에 있는경우 해결
    for r in set_reserve:
        if r-1 in set_lost:
            set_lost.remove(r-1)
        elif r+1 in set_lost:
            set_lost.remove(r+1)
    return n-len(set_lost)