[자바] 그리디 알고리즘

• 현재 상태에서 보는 선택지 중 최선의 선택을 하는 알고리즘
• 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수함
• but, 항상 최적의 해를 보장하지 못함(단점)
• => 사용하기 전 논리 유무를 살펴야

 

수행과정

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사 -> 못하면 과정 1로 돌아가기