Do it 알고리즘 코딩테스트 하루코딩 6장 그리디 이론

# 17 그리디 알고리즘 (탐욕법)

현재 단계의 선택지 중에서 최선을 선택해나가다 보면, 결과가 최선일 것이라고 가정하는 알고리즘

그러므로 결과가 항상 최선을 보장하지 않는다.

 

그러므로 그리디로 풀어도 되는지 판단해야한다.

 

과정

1. 해선택: 현재 단계에서 가장 최선인 해를 선택한다.

2. 적절성 검사: 현재 선택한 선택지가 전체 문제의 제약조건을 벗어나지 않는지 검사한다.

3. 해검사: 결과가 전체문제를 해결할 수 있는지 검사한다. 그렇지 못하면 1로 돌아가 반복한다.