탐욕(Greedy)

탐욕 알고리즘은 한가지 규칙에 의해 눈 앞에 보이는 최선만을 반복적으로 선택하여 최선의 결과를 얻어내는 알고리즘이다.

 

<Fence Repair>

긴 널빤지를 N토막 내려고한다. L1, L2, ... , Ln이 자르려고 하는 널빤지의 길이이며

널빤지의 길이는 토막들의 합과 같다. 널빤지를 자를때에는 비용이 든다.

 

21을 13과 8로 자르는 비용은 21이다.

13을 5와 8로 자르는 비용은 13이다.

 

N과 N개의 배열L이 주어질때 널빤지를 자를 수 있는 최소비용을 구하여라.

 

위 문제는 그리디를 이용하여 해결이 가능하다.

널빤지를 우리가 원하는 토막이 되게끔 자르다보면 마지막 토막이 나는 널빤지 조각이 있을 것이다. 여기에 주목하는 것이 이문제를 그리디로 풀 수 있는 요점이다.

예를들어 마지막 톱질로인해 널빤지조각이 a와b로 분리되었다. 그렇다면 이 톱질을 위해 소요된 비용은 a와 b의 길이의 합니다.

 

해결 방법

1.배열L에서 가장 짧은 판 두개를 선택한다.

2.둘을 합친 길이를 결과값에 더하고 판두개를 배열L에서 제거한다.

3.제거된 두개의 판을 합친판을 배열에 추가한다.

4.배열의 사이즈가 한개가 될때까지 위의 세단계를 반복한다. 

 

책에서는 배열의 원소를 제거하고 추가하는 부하를 없애기위해서 인덱스참조의 범위를 조작하여 실제 배열의 원소를 제거하거나 추가하지 않고 문제를 해결한다.