탐욕법 ( Greedy )

1. 개요

[그림 1] 탐욕법 ( Greedy ) 과정

 탐욕법 알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법이다. 일반적으로 머리속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy접근이 된다. 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들어 놓고 보면 그것이 최적이라는 보장은 없다.

일단 한번 선택한 것을 번복하지 않는다는 특성 때문에 대부분의 탐욕 알고리즘은 단순하며, 또한 제한적인 문제들에 적용된다. 최적화 문제 (optimization)란 가능한 해들 중에서 가장 좋은 (최대 또는 최소)해를 찾는 문제이다.

탐욕 알고리즘 동작 과정은 다음과 같다.

1. 해 선택 : 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합 (soulution set)에 추가한다.

2. 실행 가능성 검사 : 새로운 부분 해 집합이 실행가능한지 확인한다. 곧, 문제의 제약조건을 위배하지 않는지를 검사한다.

3. 해 검사 : 새로운 부분 해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 1의 해 선택부터 다시 시작한다.

---

2. 탐욕법 알고리즘 예제 1 - 배낭문제 (Knapsack Problem)

[그림 2] 배낭문제 (Knapsack Problem)

 어떤 배낭에 W 무게만큼 물건을 담을 수 있다.

물건들은 무게(Wi), 가격(Vi) 정보를 가지고 있는데, 물건들을 조합해서 담아 가격의 총합이 최대가 되게 하려고 한다.

물건들은 한 종류씩 밖에 없으며, 절대 배낭에 저장 가능한 무게를 초과해서는 안 되며, 물건을 쪼갤 수 없다고 가정한다.

[입력]

첫째 줄에 물건의 갯수 n(4개로 고정)과 배낭에 저장 가능한 무게 w(1<=W<=1000)가 입력된다.

둘째 줄부터 n줄에 걸쳐 물건의 정보가 물건의 무게(wi), 물건의 가격(vi)가 한줄에 하나의 물건씩 저장된다.

[출력]

배낭에 저장 가능한 무게 W를 초과하지 않으면서 물건의 가격의 총합의 최댓값을 출력한다.

-------------------------------------------------------------------------------------------------------------------------------------------------

순열을 이용해서 푼다. n개의 물건중에 n개를 모두 선택한다고 가정하고 그 순열을 만들면.. nPn = n! 개의 물건 순서 배열이 만들어진다.

즉, 위의 문제에서 4개의 물건이 주어지므로 총 4! 개의 물건 순서배열이 만들어진다.

물건 번호 순열을 이용해서 각 순열별로 앞에 있는 물건부터 배낭에 넣어서 저장 가능한 무게를 초과하지 않는 범위까지의 총 가격을 더해보고 그중에 가장 큰 가격을 구해주는 형태로 계산해 볼 수 있다.

int knapsack() { int sum; // 가격 합 int cnt; int valueData; int values[MAX_CNT] = { 0, }; // 가치 저장 int ary[MAX_CNT][4]; // 순열저장 cnt = makePermutaionTable(ary); for (int i = 0; i < cnt; i++) { // 변수 초기화 sum = 0; valueData = 0; for (int j = 0; j < n; j++) { sum = sum + weight[ary[i][j]]; // 무게 = 무게 + 물건의무게(1,2,3,4번) valueData = valueData + value[ary[i][j]]; if (sum > totWeight) // 만약 총 합이 제한무게를 넘어간다면 지우고 다음 순열로 이동 { valueData=valueData - value[ary[i][j]]; break; } printf(" 무게 = %d\t", sum); printf(" 가치 = %d\n", valueData); } printf("\n"); values[i] = valueData; } // values배열에서 제일 큰값 리턴 int size = sizeof(values) / sizeof(values[0]); quickSort(values, size); return values[MAX_CNT-1]; }

물건의 무게를 저장하는 배열과 물건별 가치를 저장하는 배열이 따로 파일입출력을 통해 배열에 입력되었으므로, 각 순열배열 한 방씩마다 각 가치를 더한것을 계산하여 제한 무게를 넘으면 다음 순열로 넘어가고 하는 식으로 구현하였다.

각 순열배열 한 방씩마다 각 가치를 더하는 과정이 (1) 해 선택 의 과정이며 제한 무게를 검사하는 과정이 (2) 실행 가능성 검사 가 될것이고 모두 가치를 더해서 새로 만든 가치배열에서 문제의 해를 구하는 과정이 (3) 해 검사 과정 이라고 생각하면 된다.