알고리즘 코딩테스트 핵심이론 강의 - 그리디 알고리즘

https://www.youtube.com/watch?v=8V2zw6Qxarc

📌 그리디 알고리즘

• 현재 상태에서 선택할 수 있는 선택 중 최선의 선택지를 계속 선택하다보면 전체 전택지 중 최선의 선택지가 나온다.
• 최적의 해를 보장하지는 않는다.

 

◾ 그리디 알고리즘 수행 과정

• 해 선택 : 현재 상태에서 가장 최선이라고 생각하는 해를 선택
• 적절정 검사 - 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
• 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사
  전체 문제를 해결하지 못하는 경우 다시 처음으로 돌아가(해 선택) 같은 과정을 반복한다.