코딩테스트
-
-
[파이썬 코테 대비 동아리]개념을 공부하자_"그리디"편1학년/파이썬 공부 2022. 11. 10. 15:07
그리디 그리디 ? : Greedy ( 탐욕 ) . 닉값하는 알고리즘이다 다른 건 다 모르겠고 현재 동작하는 곳 에서 최선의 선택을 하는 기법이다. 최적해를 구하는 데에 사용되는 근사적인 방법이다. 그리디를 적용하기 위한 2가지 조건 : 1. 탐욕적 선택 조건 / 2. 최적 부분 구조 조건 / 3. 상위 값 하위 값 배수 조건 < 이 세 가지를 만족 해야한다. 탐욕적 선택 속성이란, 앞의 선택이 이후의 선택에 영향을 주지 않는다는 조건이며 , 그리디한 선택이 항상 최적해를 보장해야 한다는 것이다. 최적 부분 구조 조건은, 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다는 것이다. 한마디로 그리디 알고리즘으로 풀어낸 해는 모든 경우의 수에서 최적이어야 한다. 또한 주어진 상..
728x90