탐욕적 알고리즘

탐욕 알고리즘

그리디 알고리즘은 동적 프로그래밍 사용시 지나치게 많은 일을 한다는것에서 착안된 알고리즘 이다.

각 단계에서 최선의 선택을 하는 기법이다.

각단계에서 최선의 선택이 전체의 최선을 만든다는 가정하에 시작된다.

동적 계획법보다 효율적이만 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장은 없다.

1. 탐욕적 알고리즘은 동적 계획법보다 수행시간이 훨씬 빠르다.

2. 시간이나 공간적인 제약으로 인해 최적해를 찾기어려울경우, 근사해를 찾는 용도로 쓰인다.

예시

문제

---

가장 적은 수의 동전으로 해당 액수를 구성해주는것이 최적의 해이다.

우리는 140원의 거스름돈을 만들어 줘야한다.

우리가 100원, 50원, 10원 동전을 여러개 가지고 있다는 가정하에 탐욕적알고리즘을 사용할 경우, 140원 보다 작으면서 후보 목록중에서 가장 큰 액수는 100원 짜리 동전을 선택하게 된다.

그후 남아있는 40원보다 작으면서 큰 금액인 10원짜리 동전을 4번 사용하여 140원이 만들어지게 한다.

하지만 우리가 70원짜리 동전있을경우 70원짜리 동전 2개로 140원을 구성하는것이 최적이 된다.

tempP = P                  
    // tempP 는 현재 남아있는 문제
while tempP not empty loop  
    // tempP가 남아있으면 반복 수행
    
    in subproblem tempP, decide greedy choice C 
        // tempP서 greedy로 해결책 C를 선택(C는 현재 선택가능한 최적의 해)
    Add value of C to solution // 해결책에 C의 값을 적용
    
    tempP := subproblem tempP reduced based on choice C // 남은 문제의 축소
end loop

---

알고리즘 푸는 순서

1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.

2. 각 조각마다 어떤 우선순위로 선택을 내릴지 결정한다.

3. 속성을 증명해본다.

1. 탐욕적 선택 속성

2. 최적 부분 구조

• 탐욕적 선택 속성

• 현 상태에서 답의 모든부분을 고려하지않고 탐욕적으로 선택하더라도 항상 최적해를 찾을수 있음을 증명해야한다.

• 선택한 방법과 다르게 최적해를 구할수 있다고 가정하고 우리가 선택한 방법이 최적해에 포함됨을 증명하는 방식을 주로 이용한다.

• 최적 부분 구조

  • 부분 문제의 최적해에서 전체문제의 최적해를 만들수 있음을 보여야한다.

  • 현 상태에서 다음 상태로 넘어간 후에도 탐욕적 알고리즘을 통해 최적해로 나아갈수 있어야 한다.