그리디(Greedy, 탐욕) 알고리즘

1. 그리디(탐욕) 알고리즘이란?

결정을 내려야 할 때마다 지금 당장 최선인 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

나중의 결과는 고려하지 않고, 오로지 현재 시점에서의 지역적인 최적해를 찾아가는 것이 특징.

출처: https://velog.io/@falling_star3/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm

 

2. 그리디 알고리즘의 핵심 이론

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 그렇지 않다면 1번으로 돌아간다.

 

 

3. 대표적인 예시

• 동전 거스름돈 문제: 동전 개수를 최소한으로하여 거스름돈을 주는 문제.

예를 들어, 1260원을 거슬러 줘야 하고 동전 단위가 500원, 100원, 50원, 10원이라면, 가장 큰 단위의 동전부터 최대한 많이 채우는 것이 "탐욕적인" 선택입니다.

 

4. 그리디 알고리즘의 한계

빠르고 간결하지만, 항상 최적의 해를 보장하지는 않는다.

예를 들어, 거스름돈 문제에서 동전 단위가 500원, 400원, 100원이고 800원을 거슬러 줘야 한다면

• 그리디 : 500원 1개 + 100원 3개 = 총 4개
• 진짜 최적의 해 : 400원 2개 = 총 2개

현재의 최선이 미래의 발목을 잡는 경우, 그리디가 아닌 DP(다이나믹 프로그래밍)이나 그래프 탐색을 고려해야 한다.