[알고리즘] 21. 탐욕 알고리즘

공부한 날짜: 2021. 11. 08

 

1. 탐욕 알고리즘 

: 최적화 문제의 답을 얻기 위해 사용하며, '탐욕'은 각 단계의 부분 문제를 풀 때 근시안 적으로 최적해를 구한다고 해서 붙여진 이름이다. 

 

-동작 순서

(1) 해 선택: 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가한다 

(2) 실행 가능성 검사: 새로운 부분해 집합이 실행가능한지를 확인. 문제의 제약 조건을 위반하지 않는지를 검사

(3) 해 검사: 새로운 부분해 집합이 문제의 해가 되는지를 확인. 아직 전체 문제의 해가 완성되지 않았다면 (1) 단계부터 다시 시작. 

 

-편의점 점원의 거스름돈 줄이기 구현