그리디 알고리즘이란? |
탐욕법이라고도 불리며 말 그대로 눈 앞의 가장 큰 이익을 추구하는 기법
최적해를 구하는데 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 방법
어떠한 명백한 알고리즘이 있는것이 아니고 방법론으로 봐야할 듯
근사적인 방법의 한계 |
그리디 알고리즘은 뒷 상황은 생각하지 않고 당장 눈앞의 이익만을 추구하는 알고리즘이다.
하지만 당장의 최적의 방법을 선택하는게 최종적으로 최적의 방법이 되리란 보장이 없다.
예제 1)
각 그림의 적힌 숫자는 문제를 푸는데 걸리는 시간이고 우리는 가장 빠른 시간안에 level1, level2, level3문제를 하나씩 해결하려 한다. 이때 문제를 푸는 시간을 최소화 하려면 어떻게 해야 할까?
앞서 설명했듯이 그리디는 뒷 상황은 생각하지 않는다. 단순히 눈 앞의 이익만을 추구하는 알고리즘이다. 그래서 그리디 알고리즘을 적용한다면 아래와 같이 될 것이다. 총 45분이 소요된다.
그렇지만 실제로 문제를 푸는 시간을 최소화 하는 방법은 아래와 같다. 42분이 소요된다.
즉 당장에 최적의 해일지라도 최종적으로는 최적의 해가 아닌 경우가 너무나도 많다.
그리디 알고리즘은 언제 쓰이나? |
위처럼 근사적인 방법으로써 한계가 있음에도 이 알고리즘은 단순한만큼 실행시간이 아주 빠르다.
그러므로 그리디를 사용하려면 그리디를 사용한 방법이 정답이 되리라는 보장이 있어야만 사용할 수 있다.
즉 특정 상황에서만 사용할 수 있다.
어떨때 쓸수있다라고 명확하게 말할 수 있는 개념이라기보다 명백히 그리디가 최적의 알고리즘이라는걸 판단하는 능력이 중요해보인다.
예제 2)
500원, 100원, 10원 동전이 무수히 많다고 가정할 때 가장 적은 수의 동전을 이용해서 1410원을 만든다고 하자. 이때 사용하는 동전의 개수는 몇개인가?
이 문제를 접했다면 일반적으로 500원을 사용할 수 있는 한도까지 사용할 것이다. 그래서 500원짜리 2개로 1000원을 만들고, 100원짜리 4개로 400원을, 10원 동전 1개로 10원을 만들어 1410원을 완성할 것이다. 그래서 이 문제의 답은 7개이다. 이 문제에는 그리디 알고리즘이 사용되었다. 쓸 수 있는 동전 중 가장 액수가 큰 것부터 순서대로 사용해 나간 것이다. 이 행동을 반복하면 문제를 풀어낼 수 있다.
이 문제를 위와 같이 단순한 방법으로 풀어낼 수 있는 이유는 작은 액수 동전이 큰 액수 동전의 약수이기 때문이다. 즉, 100원 5개로 만들수 있는 액수는 500원 동전 한개로 만들 수 있다. 그렇기 때문에 큰 액수의 동전부터 사용해 나가면 가장 적은 동전을 사용한다고 보장할 수 있는 것이다.
예제 3)
500원 400원 100원 동전으로 2800원을 만든다고 가정해보자. 위에서 한 방식대로 500원 동전부터 사용을 한다면 500원 5개, 100원 3개를 이용해 총 8개의 동전을 사용한다. 하지만 가장 동전을 적게 사용하는 방법은 400원 동전을 7개 사용하는 방법이다.
즉 무작정 그리디를 사용할 경우 틀리게 되는 경우가 더 많다고 볼 수 있고 그리디를 사용하려면 그리디를 사용하는것이 최선이다라는 근거가 있어야 한다.
예제4)
어떠한 수 N이 1이 될때까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행하려고 한다.
단 두번째 연산은 N이 K로 나누어 떨어질때만 선택할 수 있다.
1) N에서 1을 뺍니다.
2) N을 K로 나눕니다.
N과 K가 주어질때 과정을 수행해야하는 최소 횟수를 구하시오.
N이 17, K가 4라면 1번과정을 통해 16이 되고, 2번과정을 통해 4가 되고, 2번과정을 통해 1이 되어 3번의 연산이 최소횟수이다.
K가 1이 아니고서야 1을 빼는것보다는 K로 나누는것이 더 빠르게 1에 접근하는것은 명백하므로 K로 나눠지는 경우는 항상 2번연산을 선택하고, 나눠지지 않을 경우만 1번연산을 선택하면 된다.
즉 그리디를 사용할 근거가 있다.
그리디를 사용할 수 있는 힌트 |
1) 현재의 선택이 다음 선택에 영향을 미치지 않는 경우(매 선택이 독립적인 경우)
2) "최대한 적은/최대한 많은"이라는 문구가 문제에 들어가는 경우가 많음, 최대/최소의 경우의 수를 구하는 경우
3) 그리디를 사용할 수 있는 조건이 주어짐(문제 내에 숨겨져있음)
4) 정렬을 한 뒤 푸는 문제가 많음(동전 문제도 동전을 내림차순으로 정렬한 뒤 사용해야 하므로)
※ 참고문헌