[9주차] 탐욕법

- 탐욕법 : 전체가 아닌 현재 상태에서 최선의 선택을 하는 알고리즘으로 전체 탐색보다는 빠르지만 반드시 정답을 도출하지는 않음(탐욕법이 적용 가능한 문제인지 아닌지를 판별할 수 있어야 함)

 

- 앞의 선택이 뒷 선택에 영향을 주는 경우 동적 계획법 사용

- 앞의 선택이 뒷 선택에 영향을 주지 않는 경우 탐욕법 사용

 

- 탐욕법의 조건 : 각 부분에서의 선택이 다른 부분에 영향을 주지 않음, 각 부분에서의 최적 해결이 최종 해결방법

 

<탐욕법 사용 가능한 예제>

- 교환 가능한 동전의 최소 갯수 → 동전들이 서로 간 배수인 경우에 탐욕법 적용 가능

- 가능한 많은 수의 회의 시간 

- 카드 게임(A가 얻을 수 있는 최대 점수 구하기)