그리디 알고리즘(Greedy Algorithm)의 이해와 적용

그리디 알고리즘

greedy(욕심많은, 욕심쟁이의) 알고리즘 뜻 그대로

선택의 이후를 고려하지 않고 순간 순간마다의 최적의 해를 찾는 방식이다

 

그리디 알고리즘의 이해

그리디 알고리즘은 동적 계획법을 보완하는 개념이다

브루트 포스, 동적 계획법 그리고 그리디 알고리즘을 비교한다

위 그림을 참고해 서울 → 부산을 가는 최소 경로를 구해보자

브루트 포스, 동적 계획법, 그리고 그리드 알고리즘을 토대로 구해볼 것이다

 

브루트 포스

서울에서 부산으로 갈 수 있는 모든 해를 구한다(왼쪽부터)

250km + 100km / 80km / 120km

200km + 100km / 80km / 120km

300km + 100km / 80km / 120km

위 9개의 값 중 최소값인 280km를 결과로 반환한다

 

동적 계획법

1항: 서울 → 대구 경로에서 최소값을 기록한다

= 250km, 200km, 300km 중 최소값을 기록

→ dp[1] = 200km

 

2항: 서울 → 부산 경로까지 최소값을 기록한다

= 200km+100km, 200km+80km, 200km+120km 중 최소값을 기록

→ dp[2] = 280km

 

그리디 알고리즘

250km / 200km / 300km 중 최소값을 구한다

100km / 80km / 120km 중 최소값을 구한다

최소값을 모두 더한다 = 280km

→ 이 문제의 경우 세가지 방법 중 가장 효율적인 방식이라 할 수 있다

 

 

그리디 알고리즘의 적용

그리디 알고리즘은 현재의 선택이 미래에 영향을 주지 않을 때 사용할 수 있다

위 문제의 경우 서울 → 대전의 1번 경로를 선택해도 대전 → 부산의 길 선택에 영향을 주는 것은 아니다매 순간의 선택이 제한조건에 영향을 주지 않을 때 순간마다 최적의 해를 구하는 경우를 알아본다

 

거스름돈 문제

철수가 10원 50원 100원 500원의 동전을 많이 가지고 있다. 4200원을 지불해야할 때 필요한 동전 개수의 최소값을 구하시오.

(알고리즘)만약 N원을 지불해야한다면 필요한 동전 개수의 최소값은 얼마인가?

 

→ 백준 문제를 짧게 만들어보았다. 500원을 사용한다고 해서 100원을 선택하지 못하는 경우가 아니다.

가장 큰 단위인 500원으로 먼저 지불한다(동전 8개)

이후 거스름돈을 다시 그 다음 큰 단위인 100원으로 지불한다(동전 2개)

그러면 총 10개로 답을 구할 수 있다

 

활동 선택 문제(Activity Selection Problem)

문제: 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력: 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2의 31승-1보다 작거나 같은 자연수 또는 0이다.

→ 백준 문제를 가져왔다. 주어진 자료량이 2의 31승(약 21억)까지 주어지기 때문에 동적계획법으로는 시간초과로 문제를 풀 수 없다.

문제를 처음 볼 때, 어떤 회의를 선택하면 다른 회의를 선택하지 못할 수도 있는데 선택이 결과에 영향을 주는 것이 아닌가? 생각할 수 있다. 하지만 더 단순화해서 [ 겹치지 않는 회의 수의 최대값을 구한다 ] → [ 가장 먼저 끝나는 회의를 처음부터 배치한다 ] 로 그리디 알고리즘의 논리로 만들 수 있다. 가장 먼저 끝나는 회의를 찾고, 그 다음으로 이어질 수 있는 회의 중 가장 먼저 끝나는 회의를 찾는 것을 반복한다면 단순탐색의 문제가 된다. 그리디 알고리즘의 경우 수학적 증명이 필수적인데 활동 선택의 경우 수학적 증명이 끝났으므로 사용할 수 있다.

 

이 외에도 배낭에 물건을 잘라서 넣을 수 있는 문제부터 최소 신장 트리 등

그리드 알고리즘의 적용은 다양하니 응용을 원한다면 문제 풀이가 필요한 것 같다