그리디 알고리즘

 

그리디의 원리

• 지금 가장 좋아보이는 선택을 하고, 한 번 선택하면 되돌아가지 않는다.

 

 

그리디가 통하는 문제와 통하지 않는 문제를 구분할 줄 알아야한다.

 

그리디가 통하는 조건

• 배수 관계

 

회의실 문제

• 핵심 - 종료 시간 빠른 순

 

 

탐욕적 선택 속성과 최적 부분 구조

• 탐욕적 선택 속성
• 최적 부분 구조

 

- 그리디인지 아닌지 헷갈리면 그리디가 아니다

 

 

 

 

사례:

 

게임 개발 시 AI에서 매 턴 가장 유리한 행동

CDN, 로드밸런서, LRU(가장 오래 안 쓴 것을 버림), 광고 입찰

 

 

배수관계가 아닌 문제는 DP로 정확하게 풀 수 있다.