[알고리즘] 탐욕법 (Greedy)

[알고리즘] 탐욕법 (Greedy)

탐욕법이란 현재 상황에서의 최적해를 쫓는 알고리즘입니다.

 

하지만 현재 상황에서의 최적해만을 추구하는 것이 전체적으로 어떤 영향을 끼칠지는 고려하지 않기 때문에 항상 옳은 결과를 장담하지는 않습니다.

Local minimum & Global minimum

그래프 위 시작점 X 에서 최소값을 찾는 프로그램을 작성한다고 할 때, 탐욕법을 이용한다고 가정해보겠습니다.

 

탐욕법은 앞서 말했듯이 현재 상황에서의 최적해를 찾는 알고리즘이기 때문에 시작점 X 에서 최소값을 찾으려면 무조건 지금의 값보다 낮은 왼쪽으로 향하게 될 것입니다.

 

왼쪽으로 진행하던 점 X 는 어느 순간 값이 커지는 변곡점을 맞게 될 것이고, 프로그램은 해당 변곡점을 그래프의 최소값이라고 생각할 것입니다.

 

하지만 위 그래프를 전체적으로 봤을때 그 변곡점은 local minimum 에 해당하는 점 A 일 것이며, 그래프의 실제 최소값은 global minimum 에 해당하는 점 B 일 것입니다.

 

탐욕법은 전체적인 부분을 고려하지 않고 현재 상황에서의 최적해만을 쫓기 때문에 위와 같은 예제에서는 알맞은 풀이법이 아니라고 볼 수 있습니다.

그렇다면 어떤 경우에 탐욕법을 사용하는 것이 좋을까?

탐욕법은 탐욕 선택 속성 (Greedy Choice Property) 와 최적 부분 구조 (Optimal Substructure) 의 특성을 가지는 문제들을 해결할 때 활용할 수 있습니다.

- 탐욕 선택 속성 (Greedy Choice Property)

탐욕 선택 속성은 이전의 선택이 이후의 선택에 영향을 끼치지 않아야 한다는 조건입니다. 즉 탐욕적인 접근이 항상 옳은 선택이라는게 보장되어야 한다는 의미입니다.

- 최적 부분 구조 (Optimal Substructure)

최적 부분 구조는 전체 문제의 최적해가 부분 문제들의 최적해로 이루어진 경우를 얘기합니다.

 

이 말은 전체 문제를 부분적인 문제들로 나누었을 때, 부분적인 문제들의 최적해가 전체적으로 보았을 때 마찬가지로 최적해를 구성해야 한다는 의미입니다.

동전 문제

가장 보편적인 문제는 동전 문제입니다.

500원, 100원, 50원, 10원 짜리 동전만을 이용해서 주어진 금액 N 원을 구성해야 한다고 할 때, 구성할 수 있는 동전의 최소 개수를 구하라. N 은 항상 10의 배수이다.

 

가장 적은 수의 동전을 이용하여 N 원을 구성하기 위해서는 동전 중 가장 큰 동전으로 구성할 수 있는 최대값을 고려한 후, 해당 값을 뺀 나머지에서 다음 단위의 동전으로 구성할 수 있는 최대값을 고려해야 합니다.

 

이와 같이 가장 큰 단위의 동전부터 이용해 N 원을 구상한다면 탐욕법을 이용하여 문제를 해결할 수 있습니다.

 

해당 문제를 탐욕법으로 접근할 수 있는 이유는 가지고 있는 동전 중 큰 단위의 동전이 항상 작은 단위의 동전의 배수이기 때문입니다.

 

그렇기 때문에 작은 단위의 동전을 조합해 이 중 큰 단위가 아닌 다른 단위의 금액을 도출해낼 수 없습니다.