그리디
각 단계마다 지역적 최적해가 궁극적으로 전역 최적 해가 되는 것
지금 state 혹은 idx에서 최선이라고 생각하는해가 결국 정답
그리디로 문제를 풀려면?
-
최적 부분 구조 (optiomal substructure)
- 이 state에서 최선을 다해 선택하는 해가 결국 전역적인 최적해로 이어지기
-
탐욕적 속성이 증명이 되어야 한다.
- 보통 귀류법으로 증명한다.
>>> 코테에선 사실상 불가능
그러면 어떻게?
-
그 지점 idx에서 가장 최적의 로직은 무엇일까?
생각하고 풀기 -
경우의 수를 따지기엔 너무나 복잡도가 큰 경우 시도하는 알고리즘
-
무식하게 풀기 > DP > 그리디
자주 활용하기
- 정렬
- 우선순위 큐
중요한 것
우디르급 태세전환!!
해가 틀리더라도 다시 시작해보기
라인스위핑
하나의 라인을 빗자루 쓸듯이 탐색하는 것만으로
점과의 집합, 선과의 집합 등 탐색을 끝내는 것
사용되는 문제
- 교차점, 점과 점의 집합 찾기 등 기하 문제
- 한번에 무언가 점이나 선들을 쓸어버리면서 문제를 풀기 !
