그리디 문제 풀기

그리디문제 풀 때 증명없이 감으로만 풀어서 문제를 계속 풀어도 실력이 제자리인 것 같았는데
책에 좋은 내용이 있어서 나중에 또 잊어버리기 전에 바로 정리해두는 게 좋을 것 같다.
(이 내용은 알고리즘 문제 해결전략 책에 나오는 내용을 참고하여 작성했습니다.)
(이 내용은 제가 이해한 걸 정리해둔 거라 틀린 내용이 있을 수도 있습니다.)

 

그리디 문제를 풀 때

(1) 탐욕적 선택 속성

(2) 최적 부분 구조 

위의 두가지를 증명하면 그리디로 풀어도 답을 구할 수 있음을 알 수 있다.

 

(1) 탐욕적 선택 속성

답의 모든 부분을 고려하지 않고 탐욕적(그 순간의 최적)으로만 선택하더라도 최적해를 구할 수 있다.

매 순간의 선택을 포함하는 최적해가 존재함을 증명해보이면 된다.

선택한 방법을 포함하지 않는 최적해의 존재를 가정하고 이를 적절히 조작해서

선택한 방법을 포함하는 최적해를 만들면 된다.

 

(2) 최적 부분 구조

최적의 선택만을 했을 때 전체문제의 최적해를 얻을 수 있다.

=부분문제의 최적해가 전체문제의 최적해를 만들 수 있음을 보여야된다.

왜냐하면 탐욕적 선택 후 남은 부분문제를 최적이 아닌 방법으로 풀어야 하는 경우도 있기 때문