Greedy Algorithm (그리디 알고리즘)

알고리즘이란 주어진 문제에 대한 최적의 해결법을 디자인하는 것이죠. 그 종류도 다양합니다. 그 중에서 그리디 알고리즘은 주어진 도메인 중에서 최선의 것을 선택하는 알고리즘을 말합니다. 그리디 알고리즘은 현재 주어진 문제에 대해서 최선의 해결책을 줄 수 있을지는 모르지만 동일한 문제에서 도메인이 변경된다면 최선의 해결책을 주지 못할 수 도 있습니다. 

코인 개수 최소화하기

유명한 문제 하나를 그리디 알고리즘을 이용해서 풀어보도록 하겠습니다. 이 문제는 어떤 가격이 주어지고, 현재 내가 가지고 있는 돈의 단위가 정해져있을 때 목표 가격을 맞추기 위해서 최소한의 코인을 사용하는 것입니다. 즉, 18원을 만들어야 하는데 10원, 5원, 2원, 1원짜리 동전이 있다고 합시다. 이때 그리디 알고리즘은 10원짜리 하나. 5원짜리 하나, 그리고 1원짜리 3개를 선택할 것입니다. 목표금액을 넘지 않는 선에서 가장 높은 금액을 선택할 테니까요. 단계별로 살펴보면 아래와 같습니다.

• 1 − 10원짜리 동전을 선택합니다. 그리고 8원이 남습니다.

• 2 − 5원짜리 동전을 선택하고, 3원이 남습니다.

• 3 − 2원짜리 동전을 선택하고, 1원이 남습니다.

• 4 − 1원짜리 동전을 선택하고, 18원을 만들었습니다.

4개의 동전을 이용해서 18원을 모았고 잘 동작하는 것처럼 보입니다. 하지만 동전의 금액 단위를 살짝 바꾸면 최선의 해결책이 나오지 않을 수 있습니다.

예를 들어, 이제 1원, 7원, 10원 짜리 동전이 있다고 가정해봅시다. 목표 금액은 동일하게 18원일 경우에는 역시나 3개의 동전만으로 최선의 선택을 할 수 있습니다. 하지만 목표 금액이 15원이라면? 그리디 알고리즘을 이용하면 10원 + 1원 + 1원 + 1원 + 1원 + 1원 을 선택하게 되므로 총 6개의 동전을 사용하게 됩니다. 하지만 최선의 선택은 7원짜리 두개와 1원짜리 한개를 가지고 15원을 만드는 방법입니다. 동전이 3개만 필요하죠. 

즉, 그리디 알고리즘은 어떤 특정 도메인에서 적용 가능할 지 몰라도 비슷한 문제를 모두 해결해 주지는 않는다는 것입니다.

그리디 알고리즘으로 해결하는 문제

대부분의 네트워킹 관련 문제들은 그리디 알고리즘을 이용합니다. 그 중 몇몇을 나열해보면 다음과 같습니다 −

• 여행하는 세일즈맨 문제
• Prim's 최소 스패닝 트리 알고리즘
• Kruskal's 최소 스패닝 트리 알고리즘
• Dijkstra's 최소 스패닝 트리 알고리즘
• Graph - 맵 컬러링
• Graph - 꼭지점 커버
• Knapsack 문제
• Job 스케쥴링 문제