12. 탐욕 알고리즘 [디딤돌 자료구조와 알고리즘 with C++]

12. 탐욕 알고리즘

탐욕(Greedy) 알고리즘은 커다란 문제를 해결하기 위해 여러 단계를 나누어 해결하는 알고리즘의 하나입니다. 동적 알고리즘도 탐욕 알고리즘처럼 커다란 문제를 해결하기 위해 여러 단계로 나누어 해결할 수 있습니다. 그런데 동적 알고리즘은 현 단계에서 다음 단계로 수행할 수 있는 모든 경험을 맹목적으로 수행하는 알고리즘입니다.

 

이러한 이유로 단계의 깊이가 깊어지고 한 단계에서 다음 단계로 넘어갈 수 있는 경우에 동적 알고리즘은 매우 나쁜 성능을 보입니다.

 

하지만 탐욕 알고리즘은 현 단계에서 갈 수 있는 다음 단계들 중에 최적이라고 판단하는 하나의 단계만 수행합니다. 따라서 탐욕 알고리즘에서는 현 단계에서 다음 단계로 갈 수 있는 모든 경험 중에 선택하는 기준을 결정하는 것이 중요합니다. 어떠한 문제는 선택하는 기준을 탐욕 스럽게 결정하여 탐욕 알고리즘이라고 부르는 것입니다.

 

그런데 매 순간 최적이라고 판단하는 다음 단계를 선택하는 방법으로 전체 문제를 해결하였을 때 전체 문제에 최적이 아닐 수도 있습니다. 탐욕 알고리즘의 가치가 높아지기 위해서는 맨 순간 탐욕스럽게 선택하면서 문제를 해결할 때 전체 문제도 최적으로 해결할 수 있다는 것을 증명할 수 있어야 합니다.

 

만약 이를 증명할 수 있다면 탐욕 알고리즘은 여러 단계로 문제를 해결할 때 한 단계에서 다음 단계의 하나의 경험만 선택하여 수행하기 때문에 전체 수행 성능을 O(N^2)에서 O(N)으로 높일 수 있습니다.

 

여기에서는 매 순간 최적의 선택을 하였을 때 전체 문제도 최적으로 해결할 수 있음을 증명한 몇 개의 알고리즘을 소개할게요.

 

첫 번째 알고리즘은 최소 개수의 거스름 돈을 계산하는 알고리즘이고 두 번째는 작업 길이가 다른 여러 작업을 수행할 때 작업 수행을 제출하고 결과가 나올 때까지의 대기 시간을 최소로 만드는 알고리즘입니다. 마지막으로 그래프에서 정점과 정점 사이의 간선을 유일하게 결정하는 신장 트리를 만드는 방법 중에 최소 비용으로 만드는 최소 신장 트리 알고리즘인 프림과 크루스칼 알고리즘을 소개할 거예요.

 

거스름 돈 문제는 어떠한 상품을 판매하였을 때 최소 개수의 거스름 돈을 지불하기 위해서 어떠한 조합으로 거스름 돈을 주어야 하는지 결정하는 알고리즘입니다.

 

그리고 작업 길이가 다른 여러 작업을 수행할 때 작업 수행을 제출하고 결과가 나올 때까지의 대기 시간을 최소로 만드는 알고리즘은 운영 체제의 스케쥴링 방법 중에 하나로 SJF(Shortest Job First)알고리즘입니다.

 

마지막으로 프림과 크루스칼 알고리즘은 원본 그래프를 최소 신장 트리로 만드는 알고리즘입니다. 프림 알고리즘은 그래프의 정점을 추가하면서 최소 신장 트리를 만드는 탐욕 알고리즘이고 크루스칼 알고리즘은 그래프의 간선을 추가하면서 최소 신장 트리를 만드는 탐욕 알고리즘입니다.

 

이 책에서는 이러한 알고리즘을 이론적으로 설명하고 구체적인 코드로 구현하는 실습을 진행합니다.