그리디 알고리즘(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억)까지 주어지기 때문에 동적계획법으로는 시간초과로 문제를 풀 수 없다.
문제를 처음 볼 때, 어떤 회의를 선택하면 다른 회의를 선택하지 못할 수도 있는데 선택이 결과에 영향을 주는 것이 아닌가? 생각할 수 있다. 하지만 더 단순화해서 [ 겹치지 않는 회의 수의 최대값을 구한다 ] → [ 가장 먼저 끝나는 회의를 처음부터 배치한다 ] 로 그리디 알고리즘의 논리로 만들 수 있다. 가장 먼저 끝나는 회의를 찾고, 그 다음으로 이어질 수 있는 회의 중 가장 먼저 끝나는 회의를 찾는 것을 반복한다면 단순탐색의 문제가 된다. 그리디 알고리즘의 경우 수학적 증명이 필수적인데 활동 선택의 경우 수학적 증명이 끝났으므로 사용할 수 있다.
이 외에도 배낭에 물건을 잘라서 넣을 수 있는 문제부터 최소 신장 트리 등
그리드 알고리즘의 적용은 다양하니 응용을 원한다면 문제 풀이가 필요한 것 같다