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

그리디 알고리즘은 문제에서 요구하는 값을 빠르게 구하기 위해 현재 상황에서 최선의 방법부터 탐색하는 알고리즘입니다.

 

예를 들어, 1,10,50,100원의 동전으로 4567원을 만들기 위한 최소한의 동전 수를 구하는 문제가 있다고 합시다.

 

이 때 1원으로 4567원을 만드는 방법 먼저 구하는 것 보다는 100원으로 채울 수 있는한 가득 채우고, 그 다음 50원, 10원, 1원을 차례로 메꾸면 훨씬 빠르게 답을 구할 수 있겠죠?

 

그리디 알고리즘은 최적의 답을 구하기 힘든 복잡한 문제에 대해 실제 답에 근사한 결과를 빠르고 간결하게 구하고 싶을 때 자주 사용됩니다.

 

<연속 부분합의 최댓값 구하기>

 

어떤 배열이 주어지고, 해당 배열속의 특정 구간의 합 중 가장 큰 값을 구하라는 문제가 있다고 가정합시다.

 이 문제에서 그리디를 사용하는 방법은 왼쪽 끝부터 차례로 구간을 확장시키면서 옆으로 나아가다가 합이 음수가 되면 멈추고 새로운 구간을 만드는 것입니다.

 위와 같은 경우에는 -5를 만난 직후 SUM이 음수가 됩니다. 이 때 여기서 3을 더하면 -2가 되지만, 새로운 구간을 3에서부터 시작한다면 SUM이 3이 됩니다(음수를 더하면 무조건 총합이 작아진다). 이로 인해 이제까지의 구간의 합이 음수라면 다음 INDEX부터 새로운 구간을 시작하는 것이 무조건 더 큰 합을 만들 수 있다는 것을 알 수 있습니다.

 

 

<구간 단위로 반전시키기>

 

 

위와 같이, 문자열이 주어지고, 구간 단위로 뒤집을 수 있을 때(0은 1로, 1은 0으로) 최소한의 횟수로 뒤집어서 원하는 문자열을 만드는 문제가 있다고 하자. 

 

첫번째 방식과 같이 전체를 뒤집은 후, 특정 구간을 뒤집는 것도 가능하지만, 밑에처럼 원하는 배열과 다른 구간만 뒤집는 경우도 가능하다. 어떤 수를 뒤집고, 또 뒤집으면 원래의 자기 자신으로 돌아오므로, 이와 같은 반복은 최대한 일어나지 않게 하는 것이 좋다. 따라서 일치하지 않는 문자의 구간의 수가 최소한의 횟수와 같다고 볼 수 있다.

 

<Fractional Knapsack>

위와 같이 보석들이 주어지고, 이를 담을 수 있는 가방이 주어졌다고 하자.

이 보석들을 쪼갤 수 있을 때 가방에 담을 수 있는 보석의 가치의 최댓값을 구하는 문제가 있다.

이 때는 보석 각각의 가격/ 무게를 계산해서, 무게대비 가격이 많이 나가는 순서대로 정렬한 후 효율이 높은 보석 순서대로 가방에 넣으면 된다.

 

<숫자합치기>

 

 숫자 합치기 문제는 배열이 주어졌을 때 숫자를 두개씩 합쳐서 하나의 수를 만드는 것입니다. 이 때 a라는 숫자와 b라는 숫자를 합칠 때 필요한 비용은 a+b라고 할 때 가능한 최솟값을 구해야 한다고 합시다.

 

배열이 1, 3, 8, 10 일때는 오름차순으로 정렬하고 앞에서부터 차례로 더해나가면 되지만, 50,50,50,50,일 때에는 앞에서부터 차례로 더하면 450이 되고, 앞에 두개 뒤에 두개 더하고 합치면 400으로 더 작은 방법이 존재한다. 

 

이처럼 예외 없이 최솟값을 구하려면, 수를 한 번 더할 때마다 정렬하면 된다.

 

나는 이 문제를 풀 때 priorityQueue를 사용하였다.

 

<특정 그리디를 사용해야 하는 경우>

 

 회의가 시작하는 시간과 끝나는 시간들이 주어졌을 때, 하나의 회의실에서 열릴 수 있는 회의 수의 최댓값을 구하는 문제가 있다고 하자. 

 

이렇게 주어졌을 때, 그리디로 풀 수 있는 세가지 방법이 있다.

 

1. 시작시간을 기준으로 오름차순  --> 더 늦게 시작하지만 일찍 끝나는 회의가 간과된다.

2. 회의시간을 기준으로 오름차순 --> 시작시간과 끝나는 시간이 고려되지 않는다. 

3. 끝나는 시간을 기준으로 오름차순 --> 예외가 발생하지 않는다.