그리디 알고리즘
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
그리디 해법 : 정당성 분석 중요
- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도
최적의 해를 구할 수 있는지 검토
[ 문제상황 ]
💡 루트 노드부터 시작하여 거쳐 가는 노트 값의 합을 최대로 만들고 싶다.
최적의 해!
5 + 7 + 9 = 21 최적의 해
매 상황에서 가장 큰 값 선택- 일반적인 상황에서 그리디 알고리즘은 무조건 최적의 해를 보장하지 않음
- 코딩 테스트에서는 그리디 알고리즘으로 얻은 해가 최적의 해가 되도록 문제를 구성하는 편
