[Algorithm] 그리디

그리디 알고리즘

• 그리디 알고리즘은 매번 최적의 선택을 하여 결국 결과가 최적이 되게 하는 알고리즘이다.
  또한 그리디 알고리즘은 최소 비용 신장트리, 크루스칼 알고리즘, 다익스트라 알고리즘 등 다양한 알고리즘에 응용되어 사용되므로 Greedy 특징을 잘 알아두어야한다.

하지만 그리디 알고리즘은 투포인트처럼 특정한 풀이방식이 정해져있는 알고리즘과는 다르게 문제마다 풀이방식이 다르므로 처음 접하면 어렵게 느낄 수 있는 알고리즘이다.

 

 

01. 그리디 알고리즘이란?

그리디 알고리즘은 직역하자면 탐욕 알고리즘으로 미래를 고려하지 않고 오직 현재 시점에 가장 좋은 선택을 하는 알고리즘이다.

 

[예시]

단위가 다른 동전들로 총액 K를 만들 수 있는 최소한의 동전 개수를 구한다.

1,620원을 만들려면 500원 동전 3개, 100원 동전 1개, 10원 동전 2개로 최소 개수는 6개가 된다. 

이 문제가 그리디 알고리즘의 가장 대표적인 예시인데 가장 큰 금액부터 최대한 많이 소진하고 이 때 뒤에 있는 동전들은 상관하지 않기 때문이다. 

1,620원의 경우 500원을 최대한 많이 소진하고 시작하는데 뒤에 100원이 몇 개 쓰일지, 10원이 몇 개 쓰일지, 미래의 선택에 대해서는 전혀 고려하지 않는다. 

→ 즉, 현재 내릴 수 있는 최선의 선택에 집중한다 라고 할 수 있다.

 

📍 그렇다고 해서 현재 내릴 수 있는 최선의 선택이 최고의 선택이 되는 것은 아니다.

 

[예시]

시작 지점부터 시작하여 가장 큰 수를 구하려고 한다. 

그리디 알고리즘에 따르면 첫 번째 단계에서 13과 6중 13을 고르고 두 번째 단계에서 36과 10중에서 38을 고르게 된다.

하지만, 가장 큰수는 156이다. 이처럼 그리디 알고리즘은 현재 상황에서 가장 좋은 결과가 전체를 보더라도 최선의 선택일 때 사용하는 알고리즘이다.

 

02. 그리디 사용조건

1. 현재의 선택이 미래의 선택에 영향을 주지 않는다.
2. 부분의 최적해가 모이면 전체의 최적해가 된다.

이 2가지 조건 중 하나라도 충족하면 우선 그리디 알고리즘인지 의심해봐야한다.

 

03. 그리디 사용법

그리디 알고리즘이라는 판단이 되면, 먼저 주어진 데이터를 어떻게 정렬할지 고려한다.

최적의 해를 찾아야하므로 어떤 조건으로 정렬을 해야 미래의 선택에 영향을 주지 않을지 생각한다.

 

물론 정렬이 모든 경우에서 좋은 방법은 아니지만 아이디어가 떠오르지 않을 때 우선 여러가지 방면으로 정렬을 해보면서 아이디어를 떠올려보는 것도 좋은 방법이다.