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

오늘 공부해볼 알고리즘은 Greedy Algorithm이다. 단어 Greedy의 욕심이 많다는 뜻 그대로 바로 눈앞의 가장 큰 이익만을 찾는 기법이다. 다음 단계를 생각하지 않고, 현재 단계에서 가장 최선을 선택하는 기법이다. 그리디 알고리즘은 최적의 결과를 낼 수 있고, polynomial 한 시간에 실행할 수 있다는 장점이 있지만, 항상 최적의 결과를 보장하는 것은 아니다. 예를 들어보도록 하겠다. 만약 1에서 4로 가고자 할 때 1에서 2로 가는 비용은 1이고, 1에서 3으로 가는 비용은 10이다. 그리고 2에서 4로 가는 비용은 100이고 3에서 4로 가는 비용은 1이다. 그리디 알고리즘을 사용해서 1에서 4를 가는 최소 비용의 경로를 찾는다면 1에서 2로 가는 경로를 선택할 것이다. 하지만 이 경로 때문에 2에서 3으로 가는 비용 100이 더해지므로 총비용은 최소비용이 아니게 된다. 이럴 경우 최적의 결과를 만들어내지 않는다. 따라서 그리디 알고리즘을 사용하고자 한다면 전체적인 최적해에 대해 먼저 생각을 해봐야 한다. 빠르고 쉬운 방법이지만 증명이 필요하다.

알고리즘을 수강할 때 풀었던 문제 중 유일하게 기억나는 그리디 알고리즘은 동전 문제다. 동전문제는 10원짜리, 50원짜리, 500원짜리 동전들을 사용해서 어떤 금액을 표현할 때 동전 개수를 최소로 사용하는 경우를 찾는 문제다. 어떠한 금액이 주어졌을 때, 무조건 사용할 수 있는 가장 큰 금액의 동전을 사용해야 한다. 500원이 주어졌다면 100원짜리 동전 5개보다 당연히 500원짜리 동전 1개를 택하는 것과 같은말이다. 위의 밑줄 친 부분은 어떤 한 동전종류를 사용해서 처음 주어졌던 금액에서 그 금액만큼 빼더라도 똑같이 적용되는 규칙과 같다. 이렇게 한 단계를 수행할 때 사용되는 선택의 조건이 다음 단계에서도 똑같이 적용될 수 있어야 한다. 계속해서 문제의 단계마다 같은 성질이 동일하게 보존되는지를 간단히 증명해보면 그리디 알고리즘이 사용될 수 있다.

그리디 알고리즘 중에서 동전문제는 너무 흔하기 때문에 추천문제인 1449번 수리공 항승문제(백준 온라인 저지)를 머릿속으로 간단히 풀어보겠다. 이 문제는 물이 새는 곳 N개가 주어지고 테이프의 길이 L이 주어진다. 테이프를 통해서 물이 새는 곳을 막을 때 필요한 테이프의 개수를 출력해야 한다. 물이 새는 모든 곳을 막아야 하므로 앞에서부터 물이 새는 곳을 차례대로 막으며 막을 때마다 그 테이프로 인해 커버할 수 있는 다른 물이 새는 곳들은 지나가며 마지막으로 물이 새는 곳까지 가본다. 맨 마지막에 도달했을 때 사용한 테이프의 개수가 필요한 테이프의 개수이다. 물을 막을 때 적어도 그 위치의 좌우 0.5만큼 간격을 줘야한다는 조건만 까먹지 않으면 된다.