[탐욕법] Greedy method

1. 탐욕법

 

가장 직관적인 알고리즘 설계 패러다임 중 하나임

 

원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 

만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없음.

 

그러나 모든 선택지를 고려해 보고 , 그중 전체 답이 가장 좋은 것을 찾는 두 방법과 다르게

각 단계마다 '지금' 당장 가장 좋은 방법만을 선택함

 

지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않음

 

탐욕적 알고리즘은 많은 경우 최적해를 찾지 못하고 다음과 같은 경우에만 쓸 수 있음.

 

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우,

    탐욕법은 동젹 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용

 

2. 시간이나 공간적 게약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면

    최적해 대신 적당히 괜찮은 답(근사해)을 찾는 것으로 타협 할 수있음.

    임의 답보다는 좋은답임

    (하지만 조합 탐색이나 메타 휴리스틱 알고리즘들이 더 좋은 답을 주는 경우가 많음)

 

탐욕적 알고리즘 문제를 풀 때는 알고리즘 정당성을 증명하는 과정을 연습하는게 좋다.

 

2. 정당성 증명

 

탐욕적 선택 속성 (greedy choice property)

동적 계획법처럼 답의 모든 부분을 고려하지 않고  탐욕적으로만 선택해도 최적해를 구함을 보여야함.

선택한 답과 다른 최적해가 존재함을 가정하고, 이것을 조작해서 선택한 답을 포함하는 최적해로 바꿀 수 있음.

 

최적 부분구조 (optimal substructure)

항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있음을 보여야함.

 

경우에 따라 성립하지 않는 경우도 있음. (첫 선택만 최적으로)

 

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

 

ex) 활동 선택 문제 (activity selection problem) - 회의실 예약 하나뿐인 회의실을 서로 겹치지 않는 회의들만을 선택해 최대한 많은 회의를 진행하는 문제.   완전탐색 -> 서로 겹치지 않는 회의들의 집합을 모든 부분 집합을 하나 하나 만들어 보며, 그중 회의들이 겹치지 않는 것 중에서 가장 큰 부분집합 집합의 크기가 n일때 집합의 수는 2^n이기 때문에 시간이 오래걸림 그리디 -> 가장 먼저 끝나는 회의 부터 선택하고 다시 가장 먼저 끝나는 회의를 선택하기를 반복. 증명 :  1. 가장 종료 시간(min)이 빠른 회의를 포함하는 최적해가 반드시 존재한다. min을 포함하지 않은 해가 있다고하자 이 해에 가장 앞부분을 min과 교체해도 min이 가장 종료시간이 빠르므로 이것 또한 최적해 중 하나가 된다. 2. 최적 부분구조

 

3. 탐욕적 알고리즘 레시피

 

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

 

2. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정.

    이에 대한 직관을 얻기 위해서는 예제 입력이나

    그 외의 작은 입력을 몇 개 손으로 풀어 보는 것이 효율적임.

 

3. 어떤 방식이 동작할 것 같으면 두 가지의 속성을 증명해봄

 

- 알고리즘 문제해결전략 375p