그리디 탐욕적인..! 내용 요약!
그리디
그리디 알고리즘은 문제를 해결할 때 각 단계에서 그 순간에 최선이라고 생각되는 선택을 하는 방식으로, 이 과정에서 얻은 선택들이 모여 전체 문제에 대한 최적의 해를 구하는 알고리즘!
그리디 알고리즘은 지역적 최적해를 쌓고 쌓아서 전역적 최적해를 찾는 과정!
구현
명제가 틀릴 수도 있음..! 그래서 최종병기라고 생각하기
무식하게 풀기 -> DP -> 그리디 (최종병기)
~~상태에서는 ~~가 최선이라는 명제를 생각하기
명제가 맞는지 check(눈)와 coding 검증 안되면 명제 change
조건
1. 최적 부분 구조
문제를 작은 부분 문제로 나눌 수 있으며, 그 부분 문제들의 최적해가 모여서 전체 문제의 최적 해를 이룰 수 있는 구조!
2. 탐욕 선택 속성
각 단계에서의 최적 선택이 전체 문제에 대해서도 최적의 해를 보장한다는 것을 의미한다!
전체 문제에 대해서도 최적의 해를 보장한다고 증명해야 함!
직접증명과 간접증명
직접 증명은 증명하려는 명제가 참이라는 것을 전제로 논리적인 순서에 따라 증명하는 방법
간접 증명은 귀류법과 같이 명제를 거짓이라고 가정하고 모순을 일으킴을 보여줌
but 코딩테스트에서 이럴 시간 없음;
그러니 어떤 명제를 생각하고 -> 어떠한 상태값에서 가장 최적의 로직 생각-> 명제 틀림 -> 빠르게 변경
팁
그리디 알고리즘을 쉽게 구축하는 방법 중 하나는 자주 나오는 풀이를 외우고 그걸 기반으로 푸는
것입니다. 보통 그리디는 정렬, 우선순위 큐 를 사용하는 2가지의 방법이 주로 나옵니다. 이 방법에 숙달을 먼저 하고 이 방법을 안될 경우에는 각 상태에서 최선이 되는 선택이 되는 로직을
생각해내면서 풀면 됩니다.
이건 그냥 한번 문제를 푸는 방법을 생각하는 방식을 알려주는 것 같다.. 원래 그냥 이렇게 푸는거 아닌가 뭔가 공식화 시켜준 거 같은 느낌이고 뭔가 관련 문제를 조금 풀어봐야 할 거 같당
