08 29 - nolsigan/nolsigan.github.io GitHub Wiki

Algorithm - 탐욕법

탐욕법은 가장 직관적인 알고리즘 설계 패러다임이다. 탐욕법을 사용하는 경우는 크게 두 가지로 제한된다.

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제의 경우, 탐욕법이 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다.
2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 어렵다면 근사해를 찾는 용도로 쓰인다.

탐욕법의 증명

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

현 상태에서 답의 모든 부분을 고려하지 않고 탐욕적으로 선택하더라도 항상 최적해를 찾을 수 있음을 증명해야한다. 선택한 방법과 다르게 최적해를 구할 수 있다고 가정하고 우리가 선택한 방법이 최적해에 포함됨을 증명하는 방식을 주로 사용한다.

2. 최적 부분 구조 (optimal substructure)

부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여야 한다. 현 상태에서 다음 상태로 넘어간 후에도 탐욕법을 통해 최적해로 나아갈 수 있어야한다.